podzielniki liczby Fermata

Podzielność. Reszty z dzielenia. Kongruencje. Systemy pozycyjne. Równania diofantyczne. Liczby pierwsze i względnie pierwsze. NWW i NWD.
bimber
Użytkownik
Użytkownik
Posty: 7
Rejestracja: 20 mar 2008, o 18:23
Płeć: Mężczyzna
Lokalizacja: kanada
Podziękował: 5 razy

podzielniki liczby Fermata

Post autor: bimber » 30 lis 2008, o 15:24

Udowodnij , ze kazdy dodatni podzielnik liczby \(\displaystyle{ 2 ^{2 ^{n} } + 1}\) ma postac \(\displaystyle{ 2 ^{n-1} k + 1}\). 2 jest napewno do potegi n - 1.
Ostatnio zmieniony 5 gru 2008, o 16:55 przez bimber, łącznie zmieniany 2 razy.

Piotr Rutkowski
Gość Specjalny
Gość Specjalny
Posty: 2234
Rejestracja: 26 paź 2006, o 18:08
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 22 razy
Pomógł: 389 razy

podzielniki liczby Fermata

Post autor: Piotr Rutkowski » 30 lis 2008, o 23:23

bimber pisze:Udowodnij , ze kazdy dodatni podzielnik liczby \(\displaystyle{ 2 ^{2 ^{n} } + 1}\) ma postac \(\displaystyle{ 2 ^{n-1} k + 1}\).
Jest to znane zadanie i bardzo instruktażowe. Poza tym mała niedokładność, tam powinno być n+1 a nie n-1.
Rozważmy naszą liczbę Fermata \(\displaystyle{ 2^{2^{n}}+1}\)
Niech \(\displaystyle{ p}\) będzie dzielnikiem pierwszym naszej liczby Fermata, natomiast \(\displaystyle{ r}\) rżedem \(\displaystyle{ 2 \ mod \ p}\). Zauważmy, że \(\displaystyle{ 2^{2^{n+1}}=(2^{2^{n}})^{2}\equiv (-1)^{2}\equiv 1 \ (modp)}\) zatem \(\displaystyle{ r|2^{n+1}}\) czyli \(\displaystyle{ r=2^{s} \ s\in \mathbb{N} s\leq n+1}\) Załóżmy, że byłoby \(\displaystyle{ s\leq n}\)
Wtedy mielibyśmy \(\displaystyle{ 2^{2^{s}}\equiv 1 \ (modp)}\) i tym bardziej po \(\displaystyle{ n-s}\) krotnym podniesieniu do kwadratu \(\displaystyle{ 2^{2^{n}}\equiv 1 \ (modp)}\) co prowadzi do sprzeczności, bo wtedy mielibyśmy \(\displaystyle{ 2^{2^{n}}\equiv 1\equiv -1 \ (modp)}\) co nam daje \(\displaystyle{ p=2}\), co jest oczywistą sprzecznością.
Otrzymalismy zatem, że \(\displaystyle{ r=2^{n+1}}\)
Dodatkowo z małego tw. Fermata \(\displaystyle{ 2^{q-1}\equiv 1 \ (modp)}\) zatem \(\displaystyle{ r|q-1}\) czyli ostatecznie \(\displaystyle{ q=2^{n+1}*k+1}\) Q.E.D.

bimber
Użytkownik
Użytkownik
Posty: 7
Rejestracja: 20 mar 2008, o 18:23
Płeć: Mężczyzna
Lokalizacja: kanada
Podziękował: 5 razy

podzielniki liczby Fermata

Post autor: bimber » 1 gru 2008, o 15:44

A jak bys to zrobil gdyby jednak bylo n - 1.

Piotr Rutkowski
Gość Specjalny
Gość Specjalny
Posty: 2234
Rejestracja: 26 paź 2006, o 18:08
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 22 razy
Pomógł: 389 razy

podzielniki liczby Fermata

Post autor: Piotr Rutkowski » 2 gru 2008, o 16:09

bimber pisze:A jak bys to zrobil gdyby jednak bylo n - 1.
No to jeśli już się bardzo uprzesz to po prostu:
\(\displaystyle{ 2^{n+1}*k+1=2^{n-1}*(4k)+1=2^{n-1}*l+1}\)
Czyli prawda, ale teza zadania jest słaba

ODPOWIEDZ