欧几里得算法是所有算法的老祖宗，因为它是流传至今的最古老的非平凡算法。

— 高德纳，《计算机程序设计艺术》第二卷（1969）

你有两根杆子，一根长 252 厘米，一根长 105 厘米，想找一把最长的尺，能把两根都恰好量整数次。用今天的话说，你要的是 最大公约数 $\gcd(252,105)$。可以把每个数的约数都列出来，再找最大的公共约数，但数一大，这就行不通了。在《几何原本》第七卷中，欧几里得教了一个快得多的方法。

用大的减去小的

欧几里得在命题 VII.1 和 VII.2 中的想法很简单：能量尽两根杆子的尺，也能量尽它们的 差。所以，不必找 252 和 105 的公共度量，可以改找 105 和 $252-105=147$ 的，再找 105 和 $147-105=42$ 的。总是用大的减去小的，直到两者相等：

$$(252,105)\to(147,105)\to(42,105)\to(42,63)\to(42,21)\to(21,21).$$

两个数都变成了 21。这就是最大公约数。希腊人把这个过程称为 antanairesis，“辗转相减”。（中国古代《九章算术》中的"更相减损术"与此相同。）

用除法的版本

多次减去同一个数，就是除法。把重复的减法合并成带余除法，算法就更短了：

$$\begin{aligned}252&=2\cdot105+42\\105&=2\cdot42+21\\42&=2\cdot21+0\end{aligned}$$

最后一个非零余数就是最大公约数：

$$\boxed{\gcd(252,105)=21.}$$

为什么行得通

如果 $a=qb+r$，那么：

  • 每个同时整除 $a$ 和 $b$ 的数，也整除 $r=a-qb$；
  • 每个同时整除 $b$ 和 $r$ 的数，也整除 $a=qb+r$。

数对 $(a,b)$ 和 $(b,r)$ 的公约数完全相同，所以 $\gcd(a,b)=\gcd(b,r)$。那么算法为什么会 结束？因为余数是每一步都在减小的正整数，$42>21>0$，而正整数不可能无限地减小下去。总有一刻余数为零，而 $\gcd(d,0)=d$。

这个算法很快。法国人加布里埃尔·拉梅在 1844 年证明，除法的次数永远不会超过两个数中较小者位数的五倍。对一百位的数，最多只需 500 次除法。

倒推回去

这些计算还能把最大公约数写成两个数的 组合。从下往上倒推：

$$\begin{aligned}21&=105-2\cdot42\\&=105-2\cdot(252-2\cdot105)\\&=5\cdot105-2\cdot252.\end{aligned}$$

验算：$525-504=21$。一般地，对任意 $a$ 和 $b$，存在整数 $x$ 和 $y$ 使 $ax+by=\gcd(a,b)$。这就是 裴蜀等式，而倒推的过程叫作 扩展欧几里得算法。

练习：求 391 和 299 的最大公约数。

$391=1\cdot299+92$，$299=3\cdot92+23$，$92=4\cdot23+0$。最大公约数是 23。事实上，$391=17\cdot23$，$299=13\cdot23$。

练习：化简分数 252/105，并把 1 写成 12 和 5 的组合。

分子分母同除以最大公约数 21：$\frac{252}{105}=\frac{12}5$。再算 $12=2\cdot5+2$，$5=2\cdot2+1$。倒推：$1=5-2\cdot2=5-2\cdot(12-2\cdot5)=5\cdot5-2\cdot12$。验算：$25-24=1$。

来源： 《几何原本》命题 VII.1 和 VII.2，D. E. Joyce 编 · Donald E. Knuth，The Art of Computer Programming，第二卷，4.5.2 节 · Gabriel Lamé，“Note sur la limite du nombre des divisions dans la recherche du plus grand commun diviseur”，Comptes rendus 19（1844）。

欧几里得的全部主题 · ← 用正方形和矩形做代数 · 素数永远不会穷尽 →

图片来源.