Dowód, że liczby są względnie pierwsze

[Citizen]

Udowodnij, że dla wszystkich nieujemnych, liczb całkowitych \(\displaystyle{ k,l \wedge k \neq l}\) największy wspólny dzielnik liczb \(\displaystyle{ \frac{2009^{2^{k}}+1}{2} \wedge \frac{2009^{2^{l}}+1}{2}}\) jest równy 1

[smigol]

Jak się nie mylę, albo jakiejś głupoty nie strzeliłem (już trochę późno jak dla mnie ), to pójdzie w ten sposób (nie chce mi się tych wszystkich piętrusów wklepywać w LaTeX-ie, sorry ).

Oczywiście zakładamy, że wspólny dzielnik to \(\displaystyle{ d}\), czyli \(\displaystyle{ 2009^{2^{k}}+1=2dx}\),
\(\displaystyle{ 2009^{2^{l}}+1=2dy}\), oczywiście (x,y)=1
pomnóż pierwsze równanie przez \(\displaystyle{ 2009^{2^l-2^k}}\) dojdź do tego, że
\(\displaystyle{ d|2009^{2^l-2^k}}\) (*)
potem z pomnożonego pierwszego równania i drugiego oraz z (*) dostaniesz, że d|1.

Jak nie wyjdzie to sorry, najwyżej jutro poprawię, a tymczasem dobranoc

[Piotr Rutkowski]

Udowodnimy, że \(\displaystyle{ (2009^{2^{k}}+1,2009^{2^{l}}+1)=2}\)
Łatwo zauważyć, że oba wyrażenia są podzielne przez dwa, ale nie przez cztery.
Niech zatem \(\displaystyle{ 2<p\in \mathbb{P}}\) będzie takie, że:
\(\displaystyle{ (p|2009^{2^{k}}+1)\wedge (p|2009^{2^{l}}+1)}\)
Oczywistym jest, że \(\displaystyle{ (p,2009)=1}\)
Niech zatem \(\displaystyle{ r=ord_{2009}p}\)
Niech \(\displaystyle{ (l<k)\iff (l+1\leq k)}\)
Zauważmy, że skoro \(\displaystyle{ 2009^{2^{l}}\equiv -1 \ (mod \ p)}\), to
\(\displaystyle{ 2009^{2^{l+1}}\equiv 1 \ (mod \ p)}\), a zatem
\(\displaystyle{ r|2^{l+1}}\) i co za tym idzie \(\displaystyle{ 2009^{2^{k}}+1=(2009^{2^{l+1}})^{2^{k-l-1}}+1\equiv 2 \ (mod \ p)}\)
Sprzeczność z założeniem dowodzi tezy zadania