Podzielność liczb

[agnieszka778]

Witam, mam do zrobienia zadanie:

Pokaż, że jeśli \(\displaystyle{ m = nq + r}\), to \(\displaystyle{ |NWD(m, n) = NWD(n, r).}\)

Czy ktoś mi pomoże, lub też naprowadzi jak to wykonać?

[ares41]

\(\displaystyle{ (n,m)=(n,m-qn)=(n,r)}\)

[bakala12]

Niech \(\displaystyle{ d=NWD\left( m,n\right)}\)
Wówczas \(\displaystyle{ d|m}\) i \(\displaystyle{ d|n}\) zatem \(\displaystyle{ d|m-nq}\) a stąd \(\displaystyle{ d|r}\)

[agnieszka778]

Aha,czyli to można tak zapisać?

Niech \(\displaystyle{ d = NWD(m, n)}\) . Wtedy \(\displaystyle{ d|m}\) i \(\displaystyle{ d|n}\) .
Więc przez rowność \(\displaystyle{ m = nq + r}\) , mamy \(\displaystyle{ d|r}\) . Czyli \(\displaystyle{ d|n}\) i \(\displaystyle{ d|r}\) .
Jesli \(\displaystyle{ b|n}\) oraz \(\displaystyle{ b|r}\), to z rownosci \(\displaystyle{ m = nq+r}\)mamy, ze \(\displaystyle{ b|m}\). Poniewaz \(\displaystyle{ b|n}\) i \(\displaystyle{ b|m}\)
oraz \(\displaystyle{ d = NWD(m, n)}\) ,
dlatego \(\displaystyle{ b|d}\) . W ostateczności \(\displaystyle{ d = NWD(n, r)}\) .

Dziękuję za pomoc