Dowód:

Danymi są liczby $a>b>0$.

Podczas dzielenia $a$ przez $b$ mamy: $a=b\cdot q+r$, gdzie $q$ to iloraz a $r$ to reszta (czyli $a$).

Jeśli jakaś liczba $d$ dzieli $a$ i $b$, to dzieli też $r$, bo: $r=a-b\cdot q$, a jeśli $d$ dzieli $a$ i $b\cdot q$, to dzieli też ich różnicę.

Jeśli liczba $d$ dzieli $b$ i $r$, to dzieli też $a$, bo: $a=b\cdot q+r$ a jeśli $d$ dzieli oba składniki prawej strony, to dzieli ich sumę.

Zatem te same liczby dzielą $(a,b)$ i $(b,r)$.

Wniosek:$NWD(a,b)=NWD(b,r)$

Ponieważ $r=a\%b$, możemy zapisać to jako: $NWD(a,b)=NWD(b,a\%b)$.