arytmetyka ara: udowodnij niech m,n∊N₁ .Jeżeli m=qn+r , 0≤r<n , gdzie q,r∊N to NWD(m,n)=NWD(n,r)

jc: m = qn + r. nwd(m,n) | m oraz nwd(m,n) | n i dlatego nwd(m,n) | r. Ponieważ nwd(m,n) | n i nwd(m,n) | r, więc nwd(m,n) ≤ nwd(n,r). Podobnie pokazujemy, że nwd(m,n) ≥ nwd(n,r). Wniosek: nwd(m,n) = nwd(n,r).