扩展欧几里得（Bézout 系数）
数学与数论 · ax + by = gcd · 模逆元的钥匙
不只求 gcd，还要找到 x 和 y
欧几里得算法告诉我们 gcd(30, 18) = 6。Bézout 定理说得更多：一定存在整数 x, y 使 30x + 18y = 6。扩展欧几里得就是把这对系数顺手算出来——不多花一分复杂度，只是在辗转相除的回程上带点货。
下行照旧，回程带货
下行：照常做除法链 a = q·b + r，一路到 b = 0。基例：此时 gcd = a，恒等式 a·1 + 0·0 = a 白送一组系数 (x, y) = (1, 0)。回代：假设下一层已给出 b·x′ + r·y′ = g，把 r = a − q·b 代进去整理：a·y′ + b·(x′ − q·y′) = g——所以本层 (x, y) = (y′, x′ − q·y′)。一层层带上来，到顶层就是答案。
下面沿用 30, 18。点「下一步」逐步看这张回代表：先自上而下填好每层的 a, b, q；到基例行写下 (1, 0)；然后自底向上填 x, y（黄色高亮是引用的下一层系数），每层字幕都验证 a·x + b·y = 6。走到顶：x = −1、y = 2，即 30·(−1) + 18·2 = 6。右侧代码随每一步同步高亮。
| a | b | q | x | y | |
|---|---|---|---|---|---|
| 第0层 | |||||
| 第1层 | |||||
| 第2层 | |||||
| 基例 |
求整数 x, y 使 30·x + 18·y = gcd(30, 18)。先照常做除法链「下行」，再从底往上「回代」系数
1function extGcd(a: number, b: number): [number, number, number] {
2 if (b === 0) // 基例：gcd = a
3 return [a, 1, 0]; // a·1 + 0·0 = a → (x,y)=(1,0)
4 const q = Math.floor(a / b); // 下行：一步除法
5 const [g, x1, y1] = extGcd(b, a % b); // 递归求下层
6 return [g, y1, x1 - q * y1]; // 回代：(x,y) = (y', x'−q·y')
7}
求30·x + 18·y = gcd
gcd6
1 / 9
它真正的用途：模逆元
Bézout：gcd(a,b) 总能写成 ax + by；扩展欧几里得顺路求出 x, y。
回代：基例 (1, 0)；每层 (x, y) = (y′, x′ − q·y′)。
模逆元：gcd(a, m) = 1 时 ax + my = 1 →
例：extgcd(3, 7) 给 x = −2 → 3 的逆是
回代：基例 (1, 0)；每层 (x, y) = (y′, x′ − q·y′)。
模逆元：gcd(a, m) = 1 时 ax + my = 1 →
a·x ≡ 1 (mod m)，x mod m 即 a⁻¹。例：extgcd(3, 7) 给 x = −2 → 3 的逆是
−2 mod 7 = 5（3·5 = 15 ≡ 1）。 模逆元让「除法」在模运算里成为可能：解同余方程 ax ≡ c (mod m)、中国剩余定理合并同余组、以及 RSA 里由加密指数 e 反解解密指数 d ≡ e⁻¹ (mod φ(n))——配合快速幂做模幂，这两页合起来就是 RSA 数学核心的完整拼图。