Podzielność, liczby pierwsze

Podzielność. Reszty z dzielenia. Kongruencje. Systemy pozycyjne. Równania diofantyczne. Liczby pierwsze i względnie pierwsze. NWW i NWD.
witcher77
Użytkownik
Użytkownik
Posty: 4
Rejestracja: 30 lip 2019, o 20:50
Płeć: Mężczyzna
Lokalizacja: Wijewo
Podziękował: 2 razy

Podzielność, liczby pierwsze

Post autor: witcher77 »

Dla jakich liczb pierwszych \(\displaystyle{ p>2}\) liczba \(\displaystyle{ 2^{2^p}-1}\) jest podzielna przez \(\displaystyle{ p}\) ?
Ostatnio zmieniony 30 maja 2020, o 22:19 przez Jan Kraszewski, łącznie zmieniany 1 raz.
Powód: Poprawa wiadomości.
Awatar użytkownika
kerajs
Użytkownik
Użytkownik
Posty: 8570
Rejestracja: 17 maja 2013, o 10:23
Płeć: Mężczyzna
Podziękował: 306 razy
Pomógł: 3347 razy

Re: Podzielność, liczby pierwsze

Post autor: kerajs »

Podzielność zachodzi dla wszystkich liczb pierwszych:
\(\displaystyle{ 2^{2^p}-1=(3-1)^{2^p}-1=( \sum_{i=0}^{2^p} (-1)^i3^{2^p-i}) -1=(3N+(-1)^{2^p}3^{0})-1=3N+1-1=3N}\)
Awatar użytkownika
Premislav
Użytkownik
Użytkownik
Posty: 15685
Rejestracja: 17 sie 2012, o 13:12
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 195 razy
Pomógł: 5219 razy

Re: Podzielność, liczby pierwsze

Post autor: Premislav »

kerajs, przecież tak to udowodniłeś tylko podzielność przez \(\displaystyle{ 3}\), a nie o to pytano w zadaniu.
~~~~~~~~~~~~~~~~

Jedyną liczbą pierwszą \(\displaystyle{ p\equiv 3\pmod{4}}\), która spełnia warunki zadania, jest \(\displaystyle{ 3}\):
powiedzmy, że \(\displaystyle{ p\equiv 3\pmod{4}}\) spełnia \(\displaystyle{ 2^{2^{p}}\equiv 1\pmod{p}}\). Niech \(\displaystyle{ r=\mathrm{ord}_{p}(2)}\). Wówczas przez sprzeczność łatwo mamy \(\displaystyle{ r|2^{p}}\), zatem \(\displaystyle{ (\exists k\in\left\{1,2\ldots p\right\})r=2^{k}}\), a z drugiej strony z MTF zachodzi \(\displaystyle{ 2^{p-1}\equiv 1\pmod{p}}\), więc również przez sprzeczność łatwo mamy \(\displaystyle{ r|(p-1)}\).
Jednak skoro \(\displaystyle{ p\equiv 3\pmod{4}}\), to \(\displaystyle{ 4\nmid p-1}\), więc musi być \(\displaystyle{ k=1}\), tj. \(\displaystyle{ 2^{2^{1}}\equiv 1\pmod{p}}\), zatem \(\displaystyle{ p=3}\).

Dużo gorzej jest z liczbami pierwszymi \(\displaystyle{ p\equiv 1\pmod{4}}\), nic konkretnego nie udało mi się uzyskać w tym przypadku, bo jestem durniem i nie mam uzdolnień matematycznych. Twierdzenie Dirichleta dostarcza mocno nieelementarnego argumentu za tym, że jest sporo (mianowicie nieskończenie wiele) liczb pierwszych \(\displaystyle{ p=4k+1}\), dla których rozważana podzielność nie zachodzi (ustalmy \(\displaystyle{ m\in \NN^{+}}\), wtedy z Dirichleta w ciągu \(\displaystyle{ a_{n}=n\cdot 2^{m}+\left(2^{m-1}+1\right)}\) występuje nieskończenie wiele liczb pierwszych i dla takich liczb pierwszych \(\displaystyle{ p}\) mamy \(\displaystyle{ p-1\equiv 2^{m-1}\pmod{2^{m}}}\), więc jeśli chcemy, by \(\displaystyle{ 2^{2^{p}}\equiv 1\pmod{p}}\), musi być \(\displaystyle{ \mathrm{ord}_{p}(2)=2^{k}, \ k\le m-1}\), co na przykład w oczywisty sposób się sypie, gdy \(\displaystyle{ p>2^{2^{m-1}}}\)).
ODPOWIEDZ