欧几里得算法

欧几里得算法通过反复做带余除法求两个整数的最大公约数。它不必先分解质因数，因此即使整数很大，也可直接从一串余数读出答案。对整数 $a, b$ 且 $b \neq 0$ ，按除法定理写成 $a = b q + r$ ，其中 $0 \leq r < | b |$ ；核心等式为 $gcd (a, b) = gcd (b, r) .$

余数不会改变公约数

任何同时整除 $a, b$ 的整数也整除 $r = a - b q$ ；反过来，任何同时整除 $b, r$ 的整数也整除 $a = b q + r$ 。因此两对数有完全相同的公约数，其最大正公约数相同。每次把 $(a, b)$ 换成 $(b, r)$ 时，新的第二个非负数严格小于原来的 $| b |$ ，不可能无限下降，算法终会遇到零。最后一对是 $(d, 0)$ ，答案便是 $| d |$ 。

一次完整的计算

求 $gcd (252, 198)$ ： $252 = 1 \cdot 198 + 54, 198 = 3 \cdot 54 + 36,$ $54 = 1 \cdot 36 + 18, 36 = 2 \cdot 18 + 0.$ 最后一个非零余数是 18。为看清它不只是“算出来的因子”，可回代为 $18 = 54 - 36 = 54 - (198 - 3 \cdot 54) = 4 \cdot 54 - 198 = 4 \cdot 252 - 5 \cdot 198.$ 这给出了贝祖等式的一组系数，并说明 252 与 198 的任何公约数都整除 18；反向检查 $252 = 14 \cdot 18$ 、 $198 = 11 \cdot 18$ ，所以 18 确实是最大公约数。回代也是扩展欧几里得算法求模逆元的起点。

零、负数与终止速度

本篇约定 $gcd (a, b)$ 为非负数，且两数不同时为零。于是 $gcd (a, 0) = | a |$ ， $gcd (0, b) = | b |$ ； $gcd (0, 0)$ 不在此定义之内。负号不影响公约数，例如 $gcd (- 252, 198) = 18$ ，实现时可先取绝对值。

对 $0 < b \leq a$ ，看连续两次除法。第一次余数若小于 $b / 2$ ，第二个参数已经减半；若第一次余数至少为 $b / 2$ ，下一次余数小于 $b - b / 2 = b / 2$ 。因此至多每两步，较小参数就减至一半以下，除法次数为 $O (\log b)$ 。这与试除所有可能因子相比，解释了算法在大整数上的效率。

可运行的实现

函数接收任意两个不全为零的 Python 整数，返回非负的最大公约数；它不修改输入，也不依赖外部库。

Python 3

def euclidean_gcd(a, b):
    if a == 0 and b == 0:
        raise ValueError("gcd(0, 0) is undefined here")
    a, b = abs(a), abs(b)
    while b:
        a, b = b, a % b
    return a

print(euclidean_gcd(252, 198))   # 18
print(euclidean_gcd(-252, 198))  # 18
print(euclidean_gcd(0, 7))       # 7

只保存当前两个整数，辅助空间为 $O (1)$ 个整数；按整数位数计量时，大整数除法自身也有成本，不能把“对数次除法”误说成固定机器时间。算法与线性同余方程衔接：先求 $gcd (a, n)$ ，就能判断 $a x \equiv b (\mod n)$ 是否可能有解。

从公约数求模逆元

算法若算出 $gcd (a, n) = 1$ ，回代到 $a u + n v = 1$ 后， $u$ 就是 $a$ 在模 $n$ 下的模逆元。例如 $65 = 2 \cdot 28 + 9, 28 = 3 \cdot 9 + 1,$ 所以 $gcd (28, 65) = 1$ 。倒过来代入， $1 = 28 - 3 (65 - 2 \cdot 28) = 7 \cdot 28 - 3 \cdot 65$ ，于是 $2 8^{- 1} \equiv 7 (\mod 65)$ 。核验 $28 \cdot 7 = 196 = 3 \cdot 65 + 1$ 。这里的“逆元”不是实数倒数 $1 / 28$ ，而是一个整数剩余类；若最大公约数大于 1，这样的整数就不存在。

可把同一过程用于约分。分数 $252 / 198$ 先用算法得公约数 18，再分子分母同除以 18，得到 $14 / 11$ 。反过来，若要自己核算代码，对 $(48, 18)$ 依次得到余数 $12, 6, 0$ ，答案 6；把输入交换成 $(18, 48)$ 时，最初一步余数为 18，然后进入完全相同的过程，答案不应改变。

“互素就有逆元”也有反向。若某个整数 $u$ 满足 $a u \equiv 1 (\mod n)$ ，则存在整数 $k$ 使 $a u - k n = 1$ 。任何同时整除 $a, n$ 的正整数也必整除右侧的 1，因而只能是 1；即 $gcd (a, n) = 1$ 。所以先运行欧几里得算法判互素，再回代求逆元，不只是常用手法，而是可解性的完整判据。例如 $6$ 在模 14 下没有逆元，因为算法第一步就会得到 $gcd (6, 14) = 2$ 。这与线性同余方程中能否直接约去系数的问题完全一致。

从程序角度核对正确性也只需抓住一个不变量：每次进入 while 循环时，当前 a, b 的最大公约数始终等于最初输入的最大公约数；赋值 a, b = b, a % b 正是前面证明的等式。当 b 变成零，a 就是那个一直未改变的公约数。这个说明比只看几个输出样例更能解释代码对所有合法输入都成立。

参考资料