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)
22 lut 17:45
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
22 lut 17:52
hjjh: a skąd wiem że NWD(n,m) = 1?
22 lut 18:17
wredulus_pospolitus:
jeżeli NWD(n,m) = j > 1
to NWD(a,b) > j*k > k
22 lut 18:21
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?
22 lut 18:44
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
22 lut 18:45
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)
22 lut 21:08