扩展欧几里得算法这名字，听起来像是个只会在数学竞赛和密码学课本里出现的东西，但实际上我工作这些年，发现它的出场频率远比想象中高：做算法题求模逆元、写安全相关逻辑算 RSA 私钥、甚至解一个简单的不定方程找整数解，翻来覆去绕不开它。教材上通常就甩给你一段递归代码，加一句“设 ax+by=gcd(a,b)，回溯求出整数解 x,y”，然后就没然后了。等你真正上手用的时候，各种坑就冒出来了：x 是负数怎么办？gcd 不整除 c 方程还有没有解？递归里 x 和 y 传参为什么是反着的？迭代写法又该怎么对应数学过程？
这篇文章我把自己从入门到实际项目里用这套算法的完整经验梳理了一遍，包括原理推导、递归和迭代两套实现、求模逆元和解不定方程的完整流程，再配上 RSA 私钥计算和中国剩余定理这两个工程里最典型的场景。代码给全，案例给足，你照着抄就能跑，跑完就知道为什么每一步要这么写。
1. 从欧几里得算法说起：扩展到底扩展了什么
1.1 先聊聊老祖宗留下的求 gcd 套路
欧几里得算法本身很简单，核心就一句话：gcd(a, b) = gcd(b, a mod b)。反复套用这个等式，把两个数越滚越小，直到某个数变成 0，另一个数就是最大公约数。我拿 252 和 105 举例子：
252 = 2 × 105 + 42 105 = 2 × 42 + 21 42 = 2 × 21 + 0所以 gcd(252, 105) = 21。这个算法的好处是效率极高，每轮至少让较大的数缩小一半，整体复杂度是 O(log min(a, b))，哪怕两个数都是几十位的长整数，也就是几百次除法的事儿，这也是为啥它能进 RSA 这类大数运算场景。
但传统欧几里得算法有个“性格缺陷”：它只告诉你最大公约数是多少，完全不关心这些余数是怎么一步步组合出来的。打个比方，你只知道一堆食材最后炖出了一锅汤，但每样食材放了多少、先后顺序是什么，它一概不管。实际工程和数学问题里，我们经常需要的不只是“gcd 是多少”，而是“gcd 能不能用原来的 a 和 b 线性组合出来，组合系数是多少”。这就是扩展欧几里得算法存在的意义。
1.2 扩展出来的核心能力：一组黄金系数
扩展欧几里得算法要解决的问题是：给定两个整数 a 和 b，求整数 x 和 y，使得：
a × x + b × y = gcd(a, b)这个等式叫裴蜀定理（Bézout's identity），它保证只要 gcd(a, b) 能被某个数整除，那对应系数的整数解就一定存在。扩展欧几里得算法的本质，就是在跑一遍标准欧几里得算法的过程中，把每一轮的商记下来，最后逆着推回去，把最大公约数重新写成 a 和 b 的线性组合。
我继续用 252 和 105 演示。从最后一步往上回溯：
21 = 105 - 2 × 42 = 105 - 2 × (252 - 2 × 105) = 5 × 105 - 2 × 252所以 exgcd(252, 105) 得到的一组系数是 x = -2，y = 5，验证一下：252 × (-2) + 105 × 5 = -504 + 525 = 21，完全正确。注意 x 是负数，这不是 bug，这是常态。后面所有“负数怎么规范化”的讨论，根源都在这里。
1.3 这套算法到底能用在哪儿
我盘点了一下实际开发里最常见的几类场景：
- 求模逆元：解 ax ≡ 1 (mod m)，这是 RSA、ElGamal 这类公钥密码算法的地基操作。
- 解线性丢番图方程：形如 ax + by = c 求整数解，工程里设计找零、资源分配这类整数规划问题会碰到。
- 中国剩余定理实现：解同余方程组时，需要求多个模数下的逆元，一步一个 exgcd。
- 分数模运算、组合数取模、以及各种数论算法内部的基础模块。
可以说，扩展欧几里得跟快速幂、素数筛一样，属于数论工具箱里的“基础款工具”，不会它，后面一堆算法都施展不开。
2. 数学推导：为什么回溯能求出系数
2.1 核心递推式的完整推导
理解扩展欧几里得，关键是抓住一个递推关系。设我们在某一步要算 exgcd(a, b)，按欧几里得算法的套路，下一步要算 exgcd(b, a mod b)。假设我们已经知道了后者的结果：
b × x' + (a mod b) × y' = gcd(b, a mod b)而 gcd(b, a mod b) = gcd(a, b)，所以等号右边不变。接下来把 a mod b 展开：
a mod b = a - ⌊a/b⌋ × b代回上面的等式：
b × x' + (a - ⌊a/b⌋ × b) × y' = gcd(a, b)把含 b 的项合并一下：
a × y' + b × (x' - ⌊a/b⌋ × y') = gcd(a, b)对比目标式 a × x + b × y = gcd(a, b)，系数就一目了然了：
x = y' y = x' - ⌊a/b⌋ × y'这就是为什么递归实现里要把 x 和 y 交换着传进去，再在回溯时做一次减法。如果你理解了这个推导，后面看代码就不会觉得“传参为什么是反的”很玄学了，那正是为了保证回溯后的 x 取到下一层的 y'。
2.2 终止条件与回溯过程拆解
递归的终止条件是 b = 0。此时 gcd(a, 0) = a，等式变成 a × x + 0 × y = a，显然取 x = 1，y = 0 就行。这是唯一一组“拍脑袋”定出来的初始值，剩下的全靠回溯一层层修正。
我还是用 252 和 105 完整走一遍递归过程，把每一层的中间结果列出来，你就能看到系数是怎么“长”出来的：
| 递归层 | 传入 (a, b) | 回溯后的 x | 回溯后的 y | 验证 |
|---|---|---|---|---|
| 第 1 层 | (252, 105) | -2 | 5 | 252×(-2)+105×5=21 |
| 第 2 层 | (105, 42) | 2 | -1 | 105×2+42×(-1)=21 |
| 第 3 层 | (42, 21) | 0 | 1 | 42×0+21×1=21 |
| 第 4 层 | (21, 0) | 1 | 0 | 21×1+0×0=21 |
从最后一行往上走，每一层的系数都保持“a 乘 x 加 b 乘 y 等于 21”这个不变量。这就是回溯法的精妙之处：不变量贯穿始终，每层只做 O(1) 的算术，总复杂度依然是 O(log min(a, b))。
2.3 系数的数量级与时间复杂度
很多人担心一个问题：递归回溯这么多次，系数会不会爆炸式增长？实测下来完全不用担心。可以证明，回溯过程中 x 和 y 的绝对值都不会超过 max(a, b) 的数量级，更精确地说，|x| ≤ b / (2 × gcd(a, b))，|y| ≤ a / (2 × gcd(a, b))（大致量级）。所以在 64 位整数范围内使用，只要 a、b 本身不超范围，系数一般也不会溢出。不过这里有个前提：如果你在循环里反复用乘法更新系数，比如我后面讲的迭代写法，中间过程确实有溢出风险，实操时用 long long 是个好习惯，Python 这种大整数语言则完全没这个顾虑。
3. 代码实现：递归、迭代与细节打磨
3.1 递归实现与传参顺序的坑
递归版本最简洁，也最贴近数学推导。我用 C++ 写一版：
long long exgcd(long long a, long long b, long long &x, long long &y) { if (b == 0) { x = 1; y = 0; return a; } long long g = exgcd(b, a % b, y, x); y -= a / b * x; return g; }这段代码里唯一反直觉的点就在递归调用：exgcd(b, a % b, y, x)，把当前帧的 y 当作下一层的 x 传进去，把当前帧的 x 当作下一层的 y 传进去。结合上一节的推导就清楚了：回溯后我们需要 x = y'、y = x' - ⌊a/b⌋ × y'，而递归返回后，下一层的 x'、y' 分别落在了当前帧的 y、x 里，正好对上公式。
我见过不少人手写这个版本时漏掉 y 的更新，或者把减法写成加法，结果算出来怎么验都不对。我的建议是写完立刻用一组小数据验证：比如 exgcd(252, 105)，预期得到 g=21, x=-2, y=5。把这一步当成单元测试写进代码里，之后怎么改都不怕。
3.2 迭代实现与数学过程的对应
递归虽然好写，但在极端情况下（a、b 相差巨大，递归深度达到几十层）也可能让人心里没底，而且某些语言环境递归栈开销大。迭代写法则完全避免了这个问题。关键思路是维护两组系数，分别对应“当前余数”和“上一个余数”的线性表示：
def exgcd_iter(a, b): # 初始化：始终维护 a*x0 + b*y0 = 当前余数 x0, y0 = 1, 0 # 当前余数初始为 a x1, y1 = 0, 1 # 上一个余数初始为 b while b: q = a // b a, b = b, a % b # 同步更新两行系数 x0, x1 = x1, x0 - q * x1 y0, y1 = y1, y0 - q * y1 return a, x0, y0我拿 a = 30, b = 12 验证一遍：30 × 1 + 12 × 0 = 30，当前余数 30；12 × 0 + 30 × 0？不对，一步步来。初始 x0=1,y0=0 对应 30，x1=0,y1=1 对应 12。第一轮 q=2，新余数 = 30 mod 12 = 6，而 6 = 30 - 2×12，所以要用“旧 30 的系数”减去 q 倍“旧 12 的系数”，也就是 x0 = x1 = 0, x1 = 1 - 2×0 = 1，y0 = y1 = 1, y1 = 0 - 2×1 = -2。现在 30×0 + 12×1 = 12? 不对，这里的对应关系要仔细捋一下。
其实迭代写法里每次循环，x0、y0 表示的是“新的更小的那个数”（即新余数）如何由原始 a、b 组合出来，x1、y1 表示的是“被减掉的较大的那个数”（即旧的 b）如何组合出来。刚才第一轮后：新余数 6 = a×1 + b×(-2)？带入 30×1 + 12×(-2) = 6，对的。而旧 b = 12 = a×0 + b×1，也对。第二轮 q=2，新余数 = 12 mod 6 = 0，6 = 12 - 2×6，此时更新系数，最终返回的 a=6, x0=1, y0=-2，验证 30×1 + 12×(-2) = 6，完美。只要保证“每轮结束时，x0,y0 组合出当前 a”，代码就不会出错。这个版本我建议在 C++、Java、Python 里都存一份，遇到递归深度恐惧症的时候直接换用。
3.3 细节打磨：负数处理、溢出防护与返回值约定
实际工程中输入不一定都是正整数。比如求模逆元时，a 和 m 可能出现在某些边界场景里带着负数进来。标准的扩展欧几里得算法对负数也能跑，只是系数符号会变得很难看，而且中间的取模运算在 C++ 里对负数是向零取整，跟数学定义不一致，容易出隐蔽 bug。
我的统一做法是：进函数前先把 a、b 都转成正数，记录符号，最后再把符号作用到结果上。具体到求模逆元这种场景，更常见的做法是直接用(a % m + m) % m把 a 规整到 [0, m-1] 再调函数，这样省心得多。另外，凡是用 64 位整数的场景，我建议所有参与运算的变量一律 long long，乘法中间结果用__int128或者 Python 的大整数兜底，别在这种地方省，溢出排错的时间成本远高于换类型的一秒钟。
返回值约定也要提前定好：我的习惯是函数返回 gcd，x、y 通过引用带出。这样调用方一眼就能判断 gcd 是否为 1、是否满足可逆条件，不用额外传指针判断成败。
4. 核心应用一：模逆元的完整求解
4.1 模逆元是什么、什么时候存在
模逆元的定义很直白：给定 a 和模数 m，如果存在整数 b 使得 a × b ≡ 1 (mod m)，那 b 就叫 a 在模 m 下的逆元，记作 a⁻¹。说白了就是在模世界里跟 a 相乘等于 1 的那个数。这个操作在 RSA 私钥计算、组合数取模、哈希一致性哈希环等场景到处都是。
存在条件是一条硬规则：只有当 gcd(a, m) = 1（即 a 与 m 互质）时，逆元才存在。原因也不难理解，a × b = 1 + k × m 移项就是 a × b - k × m = 1，根据裴蜀定理，左边能表示的最小正整数正好是 gcd(a, m)，所以 gcd 必须是 1。这也意味着，如果你算出来的 gcd 不是 1，直接放弃，别试图硬凑，数学上就不可能有解。
4.2 用扩展欧几里得求模逆元：完整案例
回到方程本身：求 a 在模 m 下的逆元，等价于解 a × x + m × y = 1。调用一次 exgcd(a, m) 得到 x，x 就是逆元。这里有个小坑：x 可能是负数，而逆元的习惯表示是 [0, m-1] 里的正整数，所以需要规范化：
long long mod_inverse(long long a, long long m) { long long x, y; long long g = exgcd(a, m, x, y); if (g != 1) { return -1; // 不存在模逆元 } x = (x % m + m) % m; // 关键：把负数规范到 [0, m-1] return x; }我举一个具体的数字例子，方便你对照验证：求 17 在模 3120 下的逆元。调用 exgcd(17, 3120)，会得到一组 x = -367，y = 2（你可以用上面的代码跑一下，或者手推一遍），因为 17 × (-367) + 3120 × 2 = 1。规范化后：
d = (-367 % 3120 + 3120) % 3120 = 2753验证一下：17 × 2753 = 46801，46801 mod 3120 = 1，完全正确。这个例子不是随便编的，它就是经典的 RSA 小参数案例，我后面在 RSA 那一节还会用到 2753 这个数。
4.3 为什么费马小定理不能通吃
很多人会问：求逆元不是还能用费马小定理吗？a^(m-2) mod m 一步幂运算就出来了，为什么要费劲写扩展欧几里得？
答案是适用条件不同。费马小定理的前提是模数 m 必须是素数，这在很多工程场景里是硬伤。比如 RSA 里计算私钥时用的模数是 φ(n)，它几乎不可能是素数；又比如你只想求 5 在模 12 下的逆元，12 不是素数，a^(12-2) 那条路直接不成立。扩展欧几里得对任意互质的 a、m 都成立，而且复杂度 O(log min(a, m)) 比快速幂 O(log m) 在常数上更小，因为每次迭代只有除法和减法。所以除非你 100% 确定模数是素数，否则我建议一律用扩展欧几里得，一条路走到底。
5. 核心应用二：线性丢番图方程
5.1 有解条件与特解计算
形如 ax + by = c 的方程，要求 x、y 都是整数，这就是线性丢番图方程。工程里遇到“要把总量 c 拆成 a 和 b 两种规格的整数份”这类问题，本质上就是在解这种方程。
第一步先算 g = gcd(a, b)。方程有整数解的充要条件是 g 整除 c，理由还是裴蜀定理那条线：ax + by 能表示的所有值都是 g 的倍数，所以 c 必须是 g 的倍数。有解的情况下，先解 ax + by = g，得到特解 x₀、y₀，然后整体放大 c / g 倍：
x' = x₀ × (c / g) y' = y₀ × (c / g)我用一个具体例子走一遍。解 6x + 15y = 9。先算 exgcd(6, 15)，结果是 g=3, x=-2, y=1，注意这里的 y=1 正是让等式 6×(-2) + 15×1 = 3 成立的那组系数。因为 9 / 3 = 3，所以：
x' = -2 × 3 = -6 y' = 1 × 3 = 3验证：6×(-6) + 15×3 = -36 + 45 = 9，成立。
5.2 通解构造与最小非负整数解
有了特解还不够，实际问题通常要的是“所有解”或者“在某个范围内的解”。通解的形式是所有做过整数规划的人都该刻进 DNA 的：
x = x' + (b / g) × t y = y' - (a / g) × t其中 t 取任意整数。为什么这么构造？因为要让 ax + by 的值不变，x 每增加 b/g，y 必须对应减少 a/g，这样 a × (b/g) + b × (-a/g) = 0，线性组合的增量正好抵消。
很多场景下我们需要最小非负整数解，比如找零问题里要 x ≥ 0 且尽量小。这时候用模运算卡范围就行：
long long step = b / g; // x 的增量步长 if (step < 0) step = -step; long long x_min = (x' % step + step) % step; // 最小非负特解 long long y_min = (c - a * x_min) / b; // 对应的 y拿上面的例子继续：x 的步长 step = 15 / 3 = 5，x' = -6，规范到 [0, 4] 区间是 (-6 % 5 + 5) % 5 = 4，对应的 y = (9 - 6×4) / 15 = -15 / 15 = -1。验证 6×4 + 15×(-1) = 24 - 15 = 9，正确。这里 y 允许是负数，如果你的业务要求 x、y 都非负，那就得额外检查通解区间内是否存在这样的组合，判断方法可以归结为一元一次不等式组求解，思路不复杂但容易算错，建议写个小函数统一处理。
6. 进阶应用：RSA 私钥计算与同余方程组
6.1 RSA 里私钥 d 的计算流程
RSA 的核心密钥生成过程里，扩展欧几里得算法的位置至关重要。简单回顾一下：选两个大素数 p、q，计算 n = p×q，再算欧拉函数 φ(n) = (p-1)(q-1)。选一个与 φ(n) 互质的公钥指数 e，然后私钥 d 要满足：
e × d ≡ 1 (mod φ(n))这不就是求 e 在模 φ(n) 下的逆元吗？一步 mod_inverse 搞定。我用教材里最经典的小参数案例：p=61, q=53，那么 n = 3233，φ(n) = 60 × 52 = 3120。取 e = 17（17 和 3120 互质，因为 gcd(17, 3120)=1，可以先用 exgcd 自检），然后：
long long e = 17, phi = 3120; long long x, y; exgcd(e, phi, x, y); // 17x + 3120y = 1 long long d = (x % phi + phi) % phi; // 输出：d = 2753得到的 d = 2753，这正是我之前在模逆元一节验证过的结果。这里有一个工程上容易忽略的点：φ(n) 本身不一定是素数，所以费马小定理那条路走不通，必须用扩展欧几里得，这个细节在真实密钥生成库的底层实现里一定会出现。
6.2 用一次 exgcd 解同余方程组（CRT 的工程实现）
中国剩余定理（CRT）解决的是同余方程组：
x ≡ a₁ (mod m₁) x ≡ a₂ (mod m₂)当 m₁、m₂ 互质时，在模 m₁×m₂ 下有唯一解。标准算法需要分别求 M₁ = m₂ 在模 m₁ 下的逆元、M₂ = m₁ 在模 m₂ 下的逆元，看起来要调两次 exgcd。但细想一下：一次 exgcd(m₁, m₂) 得到的是 m₁×t₁ + m₂×t₂ = 1，这个等式已经同时蕴含了两个逆元——m₂×t₂ ≡ 1 (mod m₁)，m₁×t₁ ≡ 1 (mod m₂)。所以一次调用就够了：
// 解 x ≡ a1 (mod m1), x ≡ a2 (mod m2), gcd(m1,m2)=1 long long t1, t2; exgcd(m1, m2, t1, t2); // m1*t1 + m2*t2 = 1 long long M = m1 * m2; long long x = (a1 * m2 % M * t2 + a2 * m1 % M * t1) % M; x = (x + M) % M; // 规范化到 [0, M-1]我验证一个具体例子：解 x ≡ 2 (mod 3)，x ≡ 3 (mod 5)。exgcd(3, 5) 得到 3×2 + 5×(-1) = 1，即 t₁=2, t₂=-1。代入公式：
x = 2×5×(-1) + 3×3×2 = -10 + 18 = 8 (mod 15)验证：8 mod 3 = 2，8 mod 5 = 3，完全正确。这个写法比教科书上“分别求逆再组合”少了一次 exgcd 调用，在需要大量解同余方程组的场景（比如 RSA-CRT 加速解密）性能收益是实打实的。
7. 常见问题与排查技巧
7.1 问题速查表
我把这些年实际用扩展欧几里得时踩过的坑和排查思路整理成一张表，遇到问题先对照一遍：
| 现象 | 可能原因 | 排查与解决 |
|---|---|---|
| 递归版算出的 x、y 验证不成立 | 回溯时漏更新 y，或 a/b 计算时用的变量已经变化 | 用 (a, b) = (252, 105) 等小数据单步调试，重点看每层回溯后的 x、y |
| 算模逆元返回负数 | 忘记做规范化(x % m + m) % m | 求逆元出口统一做一次规范化，保证结果落在 [0, m-1] |
| 模逆元不存在的判断失败 | 调用前没检查 gcd(a, m) 是否为 1 | 返回值约定为 gcd，调用方判断 g == 1 再继续 |
| 迭代版跑大数结果溢出 | 中间乘法 q*x1 超出 32 位 | 全部换 long long，必要时用 __int128 |
| 输入含负数导致结果诡异 | C++ 取模对负数向零取整，与数学定义不一致 | 入口处统一把参数规整到非负，或单独处理符号 |
| CRT 结果验证不对 | 逆元求反，或者公式里 a₁、a₂ 位置搞混 | 用 (2,3,3,5) 这类小例子验证，对比手算结果 |
7.2 几个实打实的调试经验
第一，永远先写验证函数再写业务代码。不管你是递归派还是迭代派，算完一组 (a, b, x, y) 后立刻检查a*x + b*y == gcd(a, b)，这个断言能拦截九成以上的低级错误。我在项目里甚至会专门写一个测试用例集，把 (30, 12)、(252, 105)、(17, 3120) 这些经典组合全放进去，改一次代码跑一遍回归。
第二，注意区分“数学上的模”和“C++ 里的 %”。数学上模运算结果恒为非负，而 C++ 里负数取模可能是负数。凡是涉及逆元、CRT 最终结果的，最后一步务必统一做规范化处理，这个习惯能省掉大量边界 bug。
第三，递归深度不是大问题，但也不是完全没问题。虽然 O(log min(a,b)) 深度通常只有几十层，但在某些嵌入式或结构化编程环境里，还是优先用迭代版更稳妥。别等到线上偶发栈溢出再后悔，写库代码时直接迭代版起步。
第四，当 gcd 不等于 1 时，算法并不会报错，而是静默返回一组“看起来能用”的系数。切记：调用方必须检查返回值，否则你会拿着一个根本不存在的模逆元去加密，然后得到一堆乱码，排查半天才发现是逆元那一步出了问题。
7.3 我个人沉淀的几个使用习惯
最后分享几个我自己写代码时的固定套路。求逆元我统一封装成 mod_inverse 函数，里面自带 gcd 检查和规范化，调用方不需要懂扩展欧几里得的细节，只看函数名就知道语义。解不定方程我封装成返回结构体{g, x0, y0, step_x, step_y}，把特解和步长一起带出来，方便上层直接构造通解。写算法题时我会用递归版，因为短、快、好调试；写库代码时我用迭代版，因为稳、可控、无栈风险。另外，所有涉及大数乘法的场景，我习惯先估算一下数量级再决定用 int64 还是上大整数库，别迷信“64 位够用”，在一些中间展开式里系数临时变大是常有的事。
这套算法我前前后后在各种项目里用了不下几十次，从最开始照着书本抄代码抄错，到后来闭着眼都能写对，最大的体会就是：数论算法跟业务代码不一样，它的正确性不是靠“感觉”就能保证的，而是靠严谨推导和持续验证。只要你把裴蜀定理那层关系吃透了，把递归回溯的系数变化捋顺了，剩下的纯粹是机械操作。希望这篇梳理能帮你少走点弯路，也欢迎在实践中多拿小数据验证，跑多了自然就熟了。
