Uzasadnij, że dla dowolnych liczb naturalnych b > a zachodzi równość N W D (a,b hjjh: Uzasadnij, że dla dowolnych liczb naturalnych b > a zachodzi równość N W D (a,b) = N W D (a,b− a)

wredulus_pospolitus: Niech NWD(a,b) = k oznacza to, że istnieją takie n,m ∊ N₊, że: a = n*k b = m*k NWD(n,m) = 1 w takim razie: b−a = (m−n)*k Czy potrafisz udowodnić, że NWD(n, m−n) = 1 jeżeli wiemy, że NWD(n,m) = 1

hjjh: a skąd wiem że NWD(n,m) = 1?

wredulus_pospolitus: jeżeli NWD(n,m) = j > 1 to NWD(a,b) > j*k > k

hjjh: a dlaczego tutaj NWD(n, m−n) = 1 zapisuję n i m−n a nie n*k i (m−n)k? bo zapisałem że a = n*k i b−a = (m−n)*k?

hjjh: może to głupie pytanie ale po prostu nie rozumiem czemu nie podstawiam tych wartości, które obliczyłem i jak jakby pomijam to k

jc: a≠0 lub b≠0 Niech d=NWD(a,b). d|a i d|b. Dlatego d|b−a. Zatem d jest wspólnym dzielnikiem liczb a, b−a. Dlatego d ≤ NWD(a, b−a), czyli NWD(a,b) ≤ NWD(a, b−a). Odwrotnie. Niech k= NWD(a, b−a). k|a i k|b−a. Dlatego k| a + (b−a) = b. Oznacza to, że k jest wspólnym dzielnikiem a i b. Dlatego k ≤ NWD(a,b), inaczej NWD(a,b−a) ≤ NWD(a,b). Z dwóch nierówności: NWD(a,b) ≤ NWD(a, b−a), NWD(a,b−a) ≤ NWD(a,b) wynika równość NWD(a,b−a) = NWD(a,b)