扩展欧几里得算法

扩展欧几里得算法在求 $gcd (a, b)$ 的同时，求出满足 $a x + b y = gcd (a, b)$ 的两个整数系数。普通欧几里得算法只保留余数；扩展版让每个余数始终附带“它是原始两数怎样组合出来的”这份记录。

同时更新余数和系数

起初两行分别表示 $a = 1 a + 0 b$ 与 $b = 0 a + 1 b$ 。若当前两行余数为 $r_{0}, r_{1}$ ，做带余除法 $r_{0} = q r_{1} + r_{2}$ ，就有 $r_{2} = r_{0} - q r_{1}$ ；因此两行的系数也按同一减法更新。这个不变量保证最后留下的系数确实对应最大公约数。

以 84、30 为例： $84 - 2 \cdot 30 = 24$ ，随后 $30 - 24 = 6$ ，再得余数 0。回代给出 $6 = - 84 + 3 \cdot 30$ ，算法应返回 $(6, - 1, 3)$ 。

Python 3

def extended_gcd(a: int, b: int) -> tuple[int, int, int]:
    if a < 0 or b < 0 or (a == 0 and b == 0):
        raise ValueError("a,b must be nonnegative and not both zero")
    old_r, r = a, b
    old_s, s = 1, 0
    old_t, t = 0, 1
    while r:
        q = old_r // r
        old_r, r = r, old_r - q * r
        old_s, s = s, old_s - q * s
        old_t, t = t, old_t - q * t
    return old_r, old_s, old_t

assert extended_gcd(84, 30) == (6, -1, 3)
assert extended_gcd(0, 7) == (7, 0, 1)

函数不改写输入，返回 $(g, x, y)$ ，其中 $g \geq 0$ 且 $a x + b y = g$ 。余数严格下降保证终止；除法次数随较小正输入的位数增长，通常记作 $O (\log min (a, b))$ 次整数除法，整数本身越来越大时还须另计大整数运算成本。求模逆元时只需让算法返回的 $g = 1$ ，再把 $x$ 对模数取余。

参考资料

MIT，Mathematics for Computer Science，GCD 与 Bézout 章节。
MIT 18.781，初等数论讲义。
继续阅读：最大公约数、贝祖等式、模逆元。