podzielniki liczby Fermata
-
- Użytkownik
- Posty: 7
- Rejestracja: 20 mar 2008, o 18:23
- Płeć: Mężczyzna
- Lokalizacja: kanada
- Podziękował: 5 razy
podzielniki liczby Fermata
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.
-
- Użytkownik
- Posty: 2234
- Rejestracja: 26 paź 2006, o 18:08
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 22 razy
- Pomógł: 390 razy
podzielniki liczby Fermata
Jest to znane zadanie i bardzo instruktażowe. Poza tym mała niedokładność, tam powinno być n+1 a nie n-1.bimber pisze:Udowodnij , ze kazdy dodatni podzielnik liczby \(\displaystyle{ 2 ^{2 ^{n} } + 1}\) ma postac \(\displaystyle{ 2 ^{n-1} k + 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.
-
- Użytkownik
- Posty: 2234
- Rejestracja: 26 paź 2006, o 18:08
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 22 razy
- Pomógł: 390 razy
podzielniki liczby Fermata
No to jeśli już się bardzo uprzesz to po prostu:bimber pisze:A jak bys to zrobil gdyby jednak bylo n - 1.
\(\displaystyle{ 2^{n+1}*k+1=2^{n-1}*(4k)+1=2^{n-1}*l+1}\)
Czyli prawda, ale teza zadania jest słaba