辗转相除法 又称为 欧几里得算法

一些定义

整除：如果 $a$ 整除 $b$，记为 $a\mid b$，如果 $a$ 不能整除 $b$，记为 $a \nmid b$

最大公因子：两个不同时为零的整数 $a, b$ 的最大公因子是指能同时整除 $a, b$ 的最大的整数，记为 $(a, b)$

欧几里得算法

定理：整数 $a \geqslant b > 0$，令 $r_0 = a, r_1 = b$，如果我们做带余数除法得到 $r_j = r_{j + 1} q_{j + 1} + r_{j + 2}$，且 $0 < r_{j + 2} < r_{j + 1}, j = 0, 1, 2, \cdots, n - 2$，且 $r_{n + 1} = 0$，那么 $(a, b) = r_n$，即最后一个非零余数；

从定理中我们看到通过带余数的除法，在每一步中被除数和除数被更小的数代替，这些更小的数实际上是每一步中的除数和余数，运算知道余数为零时终止；这一系列的运算产生了一系列的等数，而最大公约数就是最后一个非零的余数。

引理一

如果 $a, b, m, n \in \mathbb{Z}$，且 $c \mid a$, $c \mid b$ 则 $c \mid (ma + nb)$

证明：

因为 $c \mid a$ 且 $c \mid b$，存在整数 $e$ 和 $f$，使得 $a = ce$, $b = cf$，因此 $ma + nb = mce + ncf = c(me + nf)$

故 $c \mid (ma + nb)$

引理二

若 $a, b, c \in \mathbb{Z}$，那么 $(a + cb, b) = (a, b)$

证明：

$a, b, c$ 是整数，我们将证明 $a, b$ 的公因子与 $a + cb, b$ 的公因子相同，这就证明了 $(a + cb, b) = (a, b)$

令 $e$ 是 $a, b$ 的公因子，由 引理一 我们有 $e\mid (a + cb)$，所以 $e$ 是 $a + cb$ 和 $b$ 的公因子；

如果 $f$ 是 $a + cb$ 和 $b$ 的公因子，那么由 引理一 我们有 $f$ 整除 $(a + cb) - cb = a$，所以 $f$ 是 $a, b$ 的公因子；

故 $(a + cb, b) = (a, b)$，证毕

引理三

如果 $e$ 和 $d$ 是整数且 $e = dq + r$，其中 $q,r$ 是整数，那么 $(e, d) = (d, r)$

证明：

在 引理二 中，将 $a, b, c$ 用 $r, d, q$ 代替，即可证明；

欧几里得算法的证明

$a, b$ 是正整数，其中 $a \geqslant b$，令 $r_0 = a, r_1 = b$，那么通过带余数的除法，我们得到

假设最终一定会有一个余数为零，正是因为余数组成的序列为 $a = r_0 \geqslant r_1 > r_2 > \cdots \geqslant 0$，序列包含的向的个数不会大于 $a$，由 引理三，我们得到 $(a, b)=(r_0, r_1)=\cdots=(r_n, 0) = r_n$

因此 $(a, b) = r_n$，即最后一个非零余数；

证毕；

参考资料

• 《 Kenneth H．Rosen - 初等数论及其应用》