整数欧几里得算法 | Codeboy's Blog

形式陈述

输入为不全为零的两个整数；算法返回它们的非负最大公因数。若第二项为零，直接返回第一项的绝对值。否则，对当前整数 $a$ 与非零 $b$ ，带余除法给出唯一 $q,r$ ，使

a=bq+r, \qquad 0\le r<|b|.

且

\gcd(a,b)=\gcd(b,r).

反复用 $(a,b)\leftarrow(b,r)$ ，第二项的绝对值严格下降，最终到达零。此时第一项的绝对值就是原输入的最大公因数。把余数等式向前回代，还能求出整数 $x,y$ ，使 $ax+by$ 等于原输入的最大公因数；这一版本称为扩展欧几里得算法。

对两个非零输入，除法步数为 $O(1+\log\min(|a|,|b|))$ 。每次大整数除法的成本另由输入位数和所用算术算法决定。

直觉

算法每次换一对更小的数，却保留完整的共同约数信息。若 $d$ 整除 $a,b$ ，它也整除 $r=a-qb$ ；反过来，若 $d$ 整除 $b,r$ ，它也整除 $a=qb+r$ 。所以 $(a,b)$ 与 $(b,r)$ 的共同约数完全相同。

余数满足 $0\le r<|b|$ ，因此这种替换只能进行有限次。最终到达 $(g,0)$ 时，两数的共同约数就是 $g$ 的约数，最大者为 $|g|$ 。每条除法等式也保留着回去的路：从最后的 $g$ 逐步代回，就能把它写成原输入的整数线性组合。

例子与边界

计算 $\gcd(252,105)$ ：

252=2\cdot105+42,\quad105=2\cdot42+21,\quad42=2\cdot21.

最后一个非零余数为 $21$ 。回代时先从第二式解出它，再用第一式消去 $42$ ：

21=105-2\cdot42 =105-2(252-2\cdot105) =5\cdot105-2\cdot252.

这样既求得最大公因数，也得到 Bézout 系数。若原输入是 $-252,105$ ，则同一个等式写成 $21=2(-252)+5\cdot105$ ；先对绝对值运行算法，再恢复输入符号即可。

零输入也与终止状态相接： $(a,0)$ 直接给出 $|a|$ ， $(0,b)$ 经一次替换到达 $(b,0)$ 。本条的输入约定排除了 $(0,0)$ 。

推论与应用

求出最大公因数后，将分子、分母同时除以它，就得到最简分数。扩展版本还能求模逆：若 $ax+ny=1$ ，模 $n$ 后便得到 $ax\equiv1$ ，所以 $x$ 是 $a$ 的逆元；这样的等式存在恰好等价于 $\gcd(a,n)=1$ 。

这些逆元用于解线性同余、构造整数中国剩余定理中的坐标选择器，并参与 RSA 的指数计算。沿余数序列保留的线性关系还用于有理重构。把整数绝对值换成其他严格下降的量，同样的算法思路便推广到欧几里得整环，包括域上的一元多项式环。

保留各次带余除法的商，还能得到原有理数的简单连分数：上例的商依次为 $2,2,2$ ，因此 $252/105=[2;2,2]$ 。沿这串商逐步截断会得到收敛分数；把取整数部分与倒数的过程推广到无理数，就能进一步构造带有误差证书的有理逼近。

参考资料

Kenneth Ireland and Michael Rosen, A Classical Introduction to Modern Number Theory, 2nd ed., Springer, 1990，Ch. 1, Euclidean algorithm and continued remainders。
Ivan Niven, Herbert S. Zuckerman, and Hugh L. Montgomery, An Introduction to the Theory of Numbers, 5th ed., Wiley, 1991，Ch. 1, Euclidean and extended Euclidean algorithms。