Dowód niepodzielności.

[ares41]

Niech \(\displaystyle{ T_n=2^{2^{n}}+1}\).
Pokazać, że jeśli \(\displaystyle{ m\neq n}\) , to \(\displaystyle{ T_m \nmid T_n}\)

Uogólnić na
\(\displaystyle{ T_n= 2^{2^{.^{.^{.^{2^{n}}}}} }+1}\)

[tatteredspire]

Pierwsza część:

Wystarczy wykazać, że \(\displaystyle{ T_n,T_m}\) są względnie pierwsze o ile tylko \(\displaystyle{ m \neq n}\)

Dowód nie wprost (względnej pierwszości):

Załóżmy, że \(\displaystyle{ m>n \ge 0}\)

\(\displaystyle{ m>n \Leftrightarrow \exists_{k \in \mathbb{N}} \ m=n+k}\) - niech więc \(\displaystyle{ m=n+k}\)

Załóżmy, że \(\displaystyle{ NWD(T_m,T_n)=d}\)

\(\displaystyle{ d>1 \Rightarrow d}\) ma dzielnik będący liczbą pierwszą. Niech więc \(\displaystyle{ p\mid d}\), \(\displaystyle{ p}\) - liczba pierwsza

\(\displaystyle{ (p\mid d \wedge d\mid T_m \wedge d\mid T_n) \Rightarrow (p\mid T_m \wedge p\mid T_n)}\)

\(\displaystyle{ p\mid T_n \Leftrightarrow \exists_{s \in \mathbb{N}} \ 2^{2^n}+1=sp \Leftrightarrow \exists_{s \in \mathbb{N}} \ 2^{2^{n+k}}=(sp-1)^{2^k}}\)

Zauważ, że (można pokazać indukcyjnie) \(\displaystyle{ (sp-1)^{2^k}=zp+1}\) gdzie \(\displaystyle{ z \in \mathbb{N}}\)

Tak więc \(\displaystyle{ T_m=2^{2^{n+k}}+1=zp+2}\)

Ponieważ jednocześnie \(\displaystyle{ p\mid T_n}\) i \(\displaystyle{ T_n}\) nie jest parzyste więc i \(\displaystyle{ p}\) nie może być parzyste czyli mamy sprzeczność z tym, że \(\displaystyle{ p\mid T_m}\) gdyż \(\displaystyle{ T_m}\) daje przy dzieleniu przez \(\displaystyle{ p}\) resztę 2