ユークリッドの互除法の不変性と停止性

ステップ1（公約数の集合の一致）。$d$ を $a$ と $b$ の両方を割り切る任意の整数とし、整数 $x,y$ によって $a=dx$、$b=dy$ と書く。すると $r=a-bq=dx-dyq=d(x-yq)$ より $d\mid r$ となり、$d$ は $b$ と $r$ の両方を割り切る。逆に $d$ が $b$ と $r$ の両方を割り切り、$b=dy$、$r=dz$ と書けるなら、$a=bq+r=dyq+dz=d(yq+z)$ より $d\mid a$ となり、$d$ は $a$ と $b$ の両方を割り切る。

ステップ2（最大公約数の一致）。組 $(a,b)$ と $(b,r)$ はまったく同じ公約数の集合を持つので、その最大元も一致する:$\gcd(a,b)=\gcd(b,r)$。

ステップ3（有限回での停止）。各除法ステップの余りは $0\le r<b$ を満たすので、二つ目の数の列 $b > r_1 > r_2 > \cdots \ge 0$ は非負整数の狭義単調減少列である。このような列は高々 $b$ ステップで $0$ に達する;$\gcd(r_{k-1},r_k)=\gcd(r_k,0)=r_k$ の段階で、最後のゼロでない余り $r_k$ が $\gcd(a,b)$ となる。