Udowodnić że jeśli liczby a i b są względnie pierwsze...

laki_me · Post autor: **laki_me** » 25 wrz 2009, o 12:11

a) Wiadomo że \(\displaystyle{ NWD(x,y) = NWD(y,x)}\) oraz \(\displaystyle{ NWD(x,y) = NWD(y,x - y)}\). Udowodnić, że jeśli liczby a i b są względnie pierwsze, to również liczby \(\displaystyle{ 5b + 3a}\) i \(\displaystyle{ 8b + 5a}\) są względnie pierwsze

Zordon · Post autor: **Zordon** » 25 wrz 2009, o 12:16

policz NWD tych liczb, powinno wyjść \(\displaystyle{ NWD(5b+3a,8b+5)=NWD(a,b)}\)

miki999 · Post autor: **miki999** » 25 wrz 2009, o 12:18

\(\displaystyle{ NWD(8b+5a,5b+3a)=NWD(8b+5a-5b-3a,5b+3a)=NWD(3b+2a,5b+3a)=NWD(3b+2a,5b+3a-3b-2a)=...}\)
itd.
Pamiętaj, że \(\displaystyle{ a,\ b\ >0}\).

Pozdrawiam.

laki_me · Post autor: **laki_me** » 25 wrz 2009, o 13:29

mam policzyć podstawiając pod a i b liczby względnie pierwsze?

miki999 · Post autor: **miki999** » 25 wrz 2009, o 13:57

Nic nie masz podstawiać. Musisz poprzez wykorzystanie własności: \(\displaystyle{ NWD(x,y) = NWD(y,x - y)}\), gdzie \(\displaystyle{ x>y}\) dojść z \(\displaystyle{ NWD(5b+3a,8b+5) \ do\ NWD(a,b)}\). Czyli zawsze od większej liczby odejmujesz tę drugą- mniejszą.

Zordon · Post autor: **Zordon** » 25 wrz 2009, o 13:58

Tak, ale musisz podstawić wszystkie możliwe. Takich par jest przeliczalnie wiele, więc w skończonym czasie zdążysz udowodnić dla każdej (ustalonej pary) z nich. Zła wiadomość jest taka, że i tak się nie wyrobisz do końca życia.