[Teoria liczb] Dobra para

[mol_ksiazkowy]

Dana jest ustalona para \(\displaystyle{ (s,t)}\) liczb całkowitych, \(\displaystyle{ s \neq 0 \neq t}\) . Majac inna pare liczb całkowitych \(\displaystyle{ (x,y)}\) zastepujemy ją wg schematu \(\displaystyle{ (x,y) \mapsto (x+t,y-s)}\). Powiemy ze para \(\displaystyle{ (x,y)}\) jest szczególna , gdy po skonczonej liczbie kroków (byc moze równej zeru) uzyskamy pewna pare \(\displaystyle{ (x^\prime, y^\prime)}\) liczb które nie sa wzglednie pierwsze.
1) Zbadaj czy \(\displaystyle{ (s,t)}\) jest szczególna?
2) Wykaz ze dla dowolnej \(\displaystyle{ (s,t)}\) istnieje para \(\displaystyle{ (x,y)}\) która nie jest szczególna

[marcin7Cd]

Z 101 Nierozwiązanych zadanie 16.

Ukryta treść:    

Po n operacjach para \(\displaystyle{ (x,y)}\) staje się \(\displaystyle{ (x+nt,y-ns)}\)
1) Gdy \(\displaystyle{ NWD(s,t)>1}\) para \(\displaystyle{ (s,t)}\) jest szczególna (po \(\displaystyle{ 0}\) krokach nie są względnie pierwsze ). Gdy \(\displaystyle{ NWD(s,t)=1}\) weźmy \(\displaystyle{ p \in P}\) takie że \(\displaystyle{ p|t^2+s^2 \Leftrightarrow t^2 \equiv -s^2 \pmod{p}}\) Z uwagi na to, że \(\displaystyle{ NWD(t,s)=1}\) , to \(\displaystyle{ p \nmid t}\) oraz \(\displaystyle{ p \nmid s}\). Teraz wystarczy wziąć \(\displaystyle{ n=stm}\), gdzie \(\displaystyle{ m}\) jest takie, że \(\displaystyle{ p|1+mt^2}\) (istnieje, bo \(\displaystyle{ p \nmid t^2}\) , co się łatwo udowadnia ) i mam \(\displaystyle{ s+nt=s+st^2m=s(1+mt^2) \equiv 0 \pmod{p}}\) Jak również \(\displaystyle{ t-ns=t-ms^2t=t(1-ms^2) \equiv t(1+m(-s^2)) \equiv t(1+mt^2) \equiv 0 \pmod{p}}\). Co udowadnia, że \(\displaystyle{ (s,t)}\) jest parą szczególną
2)Oznaczmy \(\displaystyle{ s=ds_1 \ \ t=dt_1 \ \NWD(s_1,t_1)=1}\) Weźmy takie całkowite \(\displaystyle{ x}\) i \(\displaystyle{ y}\), że \(\displaystyle{ yt_1+xs_1=1}\) (istnieją, bo można wziąć \(\displaystyle{ x}\) , że\(\displaystyle{ xs_1\equiv 1 \pmod{t_1}}\), co działa, bo \(\displaystyle{ NWD(s_1,t_1)=1}\). Później wziąć takie y, aby zmniejszyć to wyrażenie do \(\displaystyle{ 1}\)). Załóżmy nie wprost, że po \(\displaystyle{ n}\) krokach para \(\displaystyle{ (x,y)}\) staje się nie względnie pierwsza, czyli istnieje \(\displaystyle{ p \in P}\), że \(\displaystyle{ p|x+ndt_1}\) i \(\displaystyle{ p|y-nds_1}\). Mnożę pierwszą podzielność przez \(\displaystyle{ s_1}\), a drugą przez \(\displaystyle{ t_1}\) i sumuję je. Otrzymuje \(\displaystyle{ p|xs_1+yt_1 \Leftrightarrow p|1}\) Sprzeczność. Oznacza to, że \(\displaystyle{ (x,y)}\) jest parą nie szczególną

Treść trochę mnie zmyliła na początku, bo myślałem, że para szczególna jest wtedy gdy po iluś krokach staje się ona względnie pierwsza i udowodniłem, że para jest szczególna dla tej definicji, gdy \(\displaystyle{ NWD(x,y,t,s)=1}\)(Czego dowód jest dużo dłuższy).