欧几里得算法的不变性与终止性

第一步(公因数集合相同)。设整数 $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$。

第二步(最大公约数相等)。由于数对 $(a,b)$ 与 $(b,r)$ 拥有完全相同的公因数集合,它们的最大元素必然相同:$\gcd(a,b)=\gcd(b,r)$。

第三步(有限步终止)。每一步带余除法产生的余数都满足 $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)$。