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}\)
Dowód niepodzielności.
-
- Użytkownik
- Posty: 716
- Rejestracja: 2 wrz 2009, o 21:59
- Płeć: Mężczyzna
- Podziękował: 83 razy
- Pomógł: 74 razy
Dowód niepodzielności.
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
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