podzielniki liczby Fermata

[bimber]

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.

[Piotr Rutkowski]

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]

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

[Piotr Rutkowski]

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