欧几里得算法这个名字，听起来有点劝退，但说白了就是辗转相除法，中学数学就见过。真正让很多人卡住的是它的进阶版——扩展欧几里得算法。我之前带过不少新人，发现不少科班同学能背出gcd(a, b) = gcd(b, a % b)，但真让他手写一个扩展欧几里得，或者解释清楚ax + by = gcd(a, b)里的x和y是怎么回溯出来的，直接就卡壳了。这篇文章打算把这两块从零讲透，用C语言一步步实现，从数学原理到代码细节全过一遍。读完你不仅能写出代码，还能明白每一步为什么这么做，遇到相关问题也有思路去排查。
1. 先搞清楚欧几里得算法到底在解决什么问题
1.1 从"最大公约数"这个老朋友说起
最大公约数，英文叫Greatest Common Divisor，缩写GCD。两个整数a和b的最大公约数，就是能同时整除a和b的那个最大的正整数。比如12和18，公约数有1、2、3、6，最大的是6，所以gcd(12, 18) = 6。这个概念从小学就开始接触了，进入编程之后它依然是个高频角色：分数的约分、判断两个数是否互质、最小公倍数的计算，全都绕不开它。
暴力求法当然也有——从1遍历到min(a, b)，找出能同时整除两者的最大数。这个方法思路简单，但效率很糟糕。你想想，如果a和b是十亿级别的数，循环就要跑十亿次，在算法竞赛或者数据处理场景里根本没法用。所以我们需要一个更聪明的办法，能在极短的时间内算出最大公约数，哪怕a和b是超大整数也没问题。
欧几里得算法就是干这件事的。它有另一个名字叫"辗转相除法"——"辗转"两个字特别形象，因为我们是在反复做除法取余，余数一点一点变小，最后归零。整个过程不需要任何素因子分解，不需要开方，只是一次又一次地做整数除法，很快就能收敛到结果。
1.2 辗转相除法为什么能一直除下去
先看这个核心公式：
gcd(a, b) = gcd(b, a % b)其中a % b是a除以b的余数。为什么这个等式成立？把a写成带余除法的形式：
a = b * q + r这里q是商，r是余数，而且0 ≤ r < b。现在假设d是a和b的一个公约数，那么d能整除a，也能整除b。看等式右边，r = a - b * q，既然d能整除a和b，那必然也能整除a减掉若干倍的b，也就是r。反过来，如果某个数d能整除b和r，那么a = b * q + r也必然能被d整除。这就说明：a和b的公约数集合，和b和r的公约数集合完全一样。公约数集合都一样了，最大的那个自然也一样，所以gcd(a, b) = gcd(b, r)。
这个推理是整个算法的心脏。每次我们用(b, a % b)替换(a, b)，数值在变小，但最大公约数不变。这个过程会一直持续到什么时候？当b变成0的时候，gcd(a, 0) = a，因为任何数都能整除0，而能整除a的最大数就是a自己。到这里，我们就得到了最终答案。
拿252和105走一遍这个过程：
252 % 105 = 42，所以gcd(252, 105) = gcd(105, 42) 105 % 42 = 21，所以gcd(105, 42) = gcd(42, 21) 42 % 21 = 0， 所以gcd(42, 21) = gcd(21, 0) = 21三步出结果。你再看一遍这几个数：252, 105, 42, 21——像不像在不断"辗转"缩小？这就是算法名字的来历。
这里我补充一个很实用的小规律：当a ≥ b的时候，a % b一定是小于a/2的。也就是说，每次迭代数值至少减半，所以整个算法的复杂度是O(log min(a, b))。哪怕a和b是连计算机都要用高精度才能存下的大数，也只需要几十次迭代就能算完。这就是为什么它能成为数论算法基石的原因。
1.3 一版能跑的C语言代码：循环版
先上一个最常用的循环实现：
#include <stdio.h> int gcd(int a, int b) { int temp; while (b != 0) { temp = b; b = a % b; a = temp; } return a; } int main() { int a = 252, b = 105; printf("gcd(%d, %d) = %d\n", a, b, gcd(a, b)); return 0; }这里有个特别容易踩的坑：temp = b; b = a % b; a = temp;这三行的顺序。很多新手直接写成a = b; b = a % b;，结果a被覆盖了，后面的a % b用的就是错误的值。你必须先把b存到临时变量里，然后用原来的a和b算出余数，最后再把原来的b赋给a。这个"先备份再更新"的思路，在做数值交换和迭代更新的时候几乎是通用准则。
为什么用b != 0当循环条件？因为算法结束条件就是第二个参数变成0，此时第一个参数就是最大公约数。这里也顺便说明一下：函数只处理非负整数就行。如果输入是负数，最大公约数按数学定义取正的就好，可以先取绝对值再调用。
1.4 递归写法与边界条件
同一算法的递归版本更短，也更接近数学定义：
int gcd(int a, int b) { if (b == 0) { return a; } return gcd(b, a % b); }递归写法的核心是边界条件。很多人写递归函数时会犹豫：边界条件到底写a == 0还是b == 0？你只要想清楚一件事——递归调用的时候，第一个参数是原来的b，第二个参数是a % b。所以第一次调用的时候，第二个参数是旧的第二个参数对第一个参数取模的结果。最终一定是第二个参数先变成0，而不是第一个参数。所以边界条件必须写在b == 0上。
提示：写递归版的欧几里得算法时，先问自己一句"递归到哪一步停？停的时候返回什么？"想清楚这两点，边界条件就不会写错。
循环版和递归版各有优势。循环版没有函数调用开销，跑大规模测试时更稳；递归版代码简洁，而且和数学公式几乎一一对应，特别适合用来理解算法思想。开发环境允许的情况下，我个人偏好递归版——因为它更"声明式"，读代码的人一眼就能看出你在实现辗转相除法。但如果是在某个性能敏感的内核模块里用，或者编译器对递归优化不好的场景，循环版更保险。两种写法都应该能默写出来，这是基本功。
2. 扩展欧几里得算法的完整推导
2.1 从gcd到不定方程：突然多出来的两个变量
欧几里得算法能求最大公约数，但生活中有些问题需要更多信息。比如经典的"凑钱问题"：给你两种面值的硬币，面值分别为a和b，要凑出某个金额，怎么凑？数学上这就是在求解不定方程：
ax + by = c其中x和y是整数，可以是负数。这类方程也叫丢番图方程。有一个重要的定理叫贝祖定理：方程ax + by = c有整数解，当且仅当c是gcd(a, b)的倍数。特别地，ax + by = gcd(a, b)一定有整数解。
问题来了：解确实存在，但到底怎么求？扩展欧几里得算法就是干这个的。它不满足于只算出gcd，还要顺便找出满足方程的一组整数x和y。这也是"扩展"二字的含义——原有的辗转相除框架不动，在这个基础上多回溯出两个系数。
为什么这个东西重要？因为后面很多应用都得靠它。最典型的是求模逆元：在密码学算法里，经常需要找一个数x，使得a * x ≡ 1 (mod m)。这本质上就是在解ax + my = 1，也就是扩展欧几里得的用武之地。不夸张地说，不理解扩展欧几里得的推导，RSA这类密码算法的核心步骤就只能停留在"背代码"的层面。
2.2 手工推演：拿18和12把回溯过程掰开揉碎
光看公式容易晕，拿具体数字一步步推一遍最有感觉。目标：求整数x和y，使得18x + 12y = gcd(18, 12)。
先走一遍普通欧几里得：
18 = 12 * 1 + 6 12 = 6 * 2 + 0所以gcd(18, 12) = 6。现在，我们要逆着这个计算过程往回走，把6表示成18和12的线性组合。
倒数第二步是18 = 12 * 1 + 6，移项得：
6 = 18 - 12 * 1这就是一组解：x = 1，y = -1。因为18 * 1 + 12 * (-1) = 6。
你看，其实只需要把除法等式移个项，答案就出来了。这个有点太简单了对吧？换一组稍微复杂点的数，比如47和36：
47 = 36 * 1 + 11 36 = 11 * 3 + 3 11 = 3 * 3 + 2 3 = 2 * 1 + 1 2 = 1 * 2 + 0gcd(47, 36) = 1。现在从最后一条除法开始，逆着往回代：
1 = 3 - 2 * 1 2 = 11 - 3 * 3把2的表达式代入1的表达式：
1 = 3 - (11 - 3 * 3) * 1 = 3 - 11 + 3 * 3 = 4 * 3 - 11再代入3的表达式。由3 = 36 - 11 * 3：
1 = 4 * (36 - 11 * 3) - 11 = 4 * 36 - 12 * 11 - 11 = 4 * 36 - 13 * 11再代入11 = 47 - 36 * 1：
1 = 4 * 36 - 13 * (47 - 36) = 4 * 36 - 13 * 47 + 13 * 36 = 17 * 36 - 13 * 47所以x = -13，y = 17。验算：47 * (-13) + 36 * 17 = -611 + 612 = 1，正确。
现在你感受到了吗？所谓回溯，就是一层一层把余数替换掉。这个过程在数学上叫"倒推"或者"回代"。真正实现成代码的时候，我们不可能真的把每一步的除法表达式都存下来再倒推——那样太占空间了。于是就有了递归版的实现：递归深入到底，然后在返回的过程中带着x、y一路算回来。
2.3 递归版扩展欧几里得的C语言实现
直接看代码：
#include <stdio.h> int exgcd(int a, int b, int *x, int *y) { if (b == 0) { *x = 1; *y = 0; return a; } int x1, y1; int g = exgcd(b, a % b, &x1, &y1); *x = y1; *y = x1 - (a / b) * y1; return g; } int main() { int a = 47, b = 36, x, y; int g = exgcd(a, b, &x, &y); printf("gcd(%d, %d) = %d\n", a, b, g); printf("%d * %d + %d * %d = %d\n", a, x, b, y, g); return 0; }代码很短，但理解它需要一点推导。看递归返回的关键部分：
假设递归调用exgcd(b, a % b, &x1, &y1)返回后，得到的等式是：
b * x1 + (a % b) * y1 = g其中g就是gcd(a, b)。现在我们要把这个等式改造成a * x + b * y = g的形式。这就要用到一个整除关系：
a % b = a - (a / b) * b把这个表达式代进去：
b * x1 + (a - (a / b) * b) * y1 = g展开括号：
b * x1 + a * y1 - (a / b) * b * y1 = g把含a的项和含b的项分别合并：
a * y1 + b * (x1 - (a / b) * y1) = g对照a * x + b * y = g，立刻得到：
x = y1 y = x1 - (a / b) * y1这就是代码里*x = y1; *y = x1 - (a / b) * y1;这两行的来历。整个过程的核心就是：下面的返回值x1、y1是上一层等式里的系数，我们要通过"余数替换"把它们转换成当前层的系数。这就是递归回溯的本质。
边界条件b == 0的时候，gcd(a, 0) = a，此时要让a * x + 0 * y = a成立，最简单的一组解就是x = 1，y = 0。
注意：递归版有个很容易被忽视的问题——用指针传参时，递归调用里的
&x1, &y1必须用新的变量。如果错误地直接把&x, &y传进去，回溯的时候原值会被覆盖，结果完全错乱。正确做法是每次递归都声明x1、y1两个"临时工人"，算完再赋值给上一层的x、y。
2.4 迭代版实现：不依赖递归回溯的另一种思路
递归版虽然优雅，但递归深度和a、b的大小有关。虽然欧几里得算法本身迭代次数是O(log min(a,b))，几十层递归一般没问题，但在某些没有良好尾递归优化的环境里，或者你对递归有心理阴影的时候，可以换成迭代版。迭代版的核心思路是维护两组系数，模拟"两行变换"的过程。
int exgcd_iter(int a, int b, int *x, int *y) { int r0 = a, r1 = b; int s0 = 1, s1 = 0; int t0 = 0, t1 = 1; while (r1 != 0) { int q = r0 / r1; int r2 = r0 - q * r1; r0 = r1; r1 = r2; int s2 = s0 - q * s1; s0 = s1; s1 = s2; int t2 = t0 - q * t1; t0 = t1; t1 = t2; } *x = s0; *y = t0; return r0; }这段代码的直观理解是：始终维护等式r0 = a * s0 + b * t0和r1 = a * s1 + b * t1。你可以在纸上验证初始值：r0 = a = a1 + b0，r1 = b = a0 + b1，成立。每一轮用q = r0 / r1生成新的r2 = r0 - qr1，同时s2 = s0 - qs1，t2 = t0 - q*t1。这样做能保证新等式依然成立。当r1变成0的时候，r0就是gcd，而s0、t0就是我们要的系数。
我个人的建议是：初学阶段先把递归版吃透，因为它和数学推导是一对一的，逻辑链最短。等彻底理解了回溯原理，再看迭代版会觉得很自然——它就是"矩阵变换"的另一种写法。如果你未来要写高性能库，迭代版没有函数调用开销，会显得更稳重。两个版本建议都自己动手写一遍，用相同输入对比输出结果是否一致。
3. 有了算法之后，拿它做什么
3.1 模逆元：密码学和竞赛题里最常见的用途
模逆元是扩展欧几里得最经典的应用场景。给定整数a和模数m，如果存在x使得：
a * x ≡ 1 (mod m)那么x就叫做a在模m下的乘法逆元，记作a⁻¹（这里不是分数，是模意义下的倒数）。求逆元的条件很严格：a和m必须互质，也就是gcd(a, m) = 1。
怎么用扩展欧几里得求？我们把同余式翻译成等式：
a * x + m * y = 1这里等式右边是1，正好是gcd(a, m)。所以用exgcd(a, m, &x, &y)求出一组解，x就是我们要的逆元。注意x可能是负数，这时需要修正到[0, m)区间：
int mod_inverse(int a, int m) { int x, y; int g = exgcd(a, m, &x, &y); if (g != 1) { printf("a 和 m 不互质，不存在逆元\n"); return -1; } return (x % m + m) % m; }这个(x % m + m) % m是处理负数取模问题时的标准模板。C语言里-7 % 3结果是-1，不是2，如果不处理直接用，后面算出来的结果就是错的。加一个m再取模，能把所有负数都掰回正数区间。
实际场景里，模逆元出现在RSA加密私钥的生成、组合数取模运算、哈希算法求随机数等地方。做题的时候最常见的需求是：要计算(a / b) % m，但b不能直接当分母除，只能乘b的逆元。这时候先调用mod_inverse(b, m)，再乘a取模，问题就解决了。
3.2 一次同余方程：标准解法直接套模板
有时候不光要单个逆元，还要解形如a * x ≡ b (mod m)的同余方程。比如在计蒜客、力扣这类平台里，处理周期性问题时经常遇到。解法分三步：
第一步，求g = gcd(a, m)。如果b % g != 0，方程无解，直接返回。为什么？因为等式右边必须是gcd的倍数才行，这是贝祖定理的直接推论。
第二步，化简。令a' = a / g，b' = b / g，m' = m / g。化简之后a'和m'互质，可以放心求逆元。
第三步，求a'在模m'下的逆元x0，然后原方程的通解是：
x ≡ x0 * b' (mod m')代码可以这样写：
int solve_linear(int a, int b, int m, int *result) { int x, y; int g = exgcd(a, m, &x, &y); if (b % g != 0) { return 0; } int a1 = a / g; int b1 = b / g; int m1 = m / g; int inv = mod_inverse(a1, m1); *result = (inv * b1 % m1 + m1) % m1; return 1; }这里有一个和数学规范不太一样但工程上很常见的点：解同余方程时，模数从m变成了m'，也就是消掉了公约数。这意味着解的空间也会变化，最后得到的result是模m'意义下的一个代表。如果题目要求给出模m意义下的解，还需要再处理一下通解形式。
3.3 顺手就能用的小应用：约分与最小公倍数
也许你会说，我暂时用不到密码学，扩展欧几里得是不是就没用了？其实日常的小工具也能用上。
最直接的是分数约分。给定分子numerator和分母denominator，先算出g = gcd(numerator, denominator)，两边同时除以g，就能得到最简分数。这个操作在实现有理数类、显示比例、处理音视频参数时非常常见。
求最小公倍数(LCM)也能用gcd：
lcm(a, b) = a / gcd(a, b) * b注意先除后乘。为什么？因为a * b可能会溢出，比如a和b都是接近int最大值的数，直接相乘就爆了。先除以gcd，把结果缩小到安全的范围内，再乘b。这个写法的顺序是无数前人踩过坑之后的经验。
在你写图形程序处理比例缩放、写电商系统做优惠分摊、写游戏程序处理冷却时间的时候，gcd和扩展欧几里得都可能在角落默默工作。这也是我把它们定义为"每个程序员都值得掌握的算法"的原因——你永远不知道下一次重构会遇到什么问题。
4. 从零基础到写对：常见错误与调试心得
4.1 递归边界和回溯顺序：两个最典型的坑
先说边界条件。我见过很多人在写扩展欧几里得时，把递归的终止条件写成了if (a == 0)。实际上正确的写法是if (b == 0)。为什么？因为递归调用是exgcd(b, a % b, ...)，第一层传进去的第二个参数是a % b，这个余数会越来越小，最终一定会变成0。如果你判断a == 0，那么在递归到最深一层时，a实际上是上一层的b，除非原始b是0，否则永远不会命中。这会导致无限递归，最终栈溢出。
再说回溯顺序。回溯公式x = y1, y = x1 - (a/b)y1。这里的x1、y1是下一层的值。很多人会写成x = x1、y = y1这种"对称"的形式，看起来好像合理，但实际上完全错误。你真要想明白：下一层的等式是bx1 + (a%b)y1 = g，我们要把它改写成ax + b*y = g，代换之后x和y的来源完全不同。x是从y1变过来的，y是从x1减去一个矫正项变过来的，千万别搞混。
我自己的调试经验是：写完之后，立刻用(long long)a * x + (long long)b * y验算结果是否等于gcd。用long long是因为中间乘积可能超出int范围。这一步是万能的检查剂，比肉眼盯代码靠谱得多。
4.2 负数、溢出和结果修正
实际使用时，传进来的a和b有可能是负数。比如求模逆元的时候，a可能是大数取模后的结果，也可能是用户传入的任意值。这时候gcd的结果按数学定义应该是正的，但扩展欧几里得算出来的x、y可能正负不定。我们的处理办法是：
- 进入函数前先把a、b取绝对值（或者统一转为非负）。
- 处理后用
(x % m + m) % m修正到正确区间。
溢出问题更隐蔽。在回溯公式x1 - (a / b) * y1里，(a / b)本身可能很大，乘以y1之后可能瞬间爆int。如果你确认输入范围比较大，用long long作为中间变量是更保险的选择。把函数签名改成：
long long exgcd(long long a, long long b, long long *x, long long *y)对绝大多数竞赛题和应用场景都够用了。
4.3 怎么验证自己写对了：我的测试习惯
算法写完之后不测试等于白写。我一般会做四层验证：
第一层，边界测试。用(0, 5)、(5, 0)、(1, 1)、(1, n)这类最基础的输入，确保函数不崩溃，结果正确。这一层能抓出80%的边界错误。
第二层，对照测试。写一个简单的穷举循环，从1到100遍历所有a、b，同时用循环版和递归版算gcd，比较结果是否一致。再验算扩展欧几里得的结果满足等式。
for (int a = 1; a <= 100; a++) { for (int b = 1; b <= 100; b++) { int x, y; int g = exgcd(a, b, &x, &y); if (a * x + b * y != g) { printf("error: gcd(%d, %d) -> %d * %d + %d * %d = %d\n", a, b, a, x, b, y, a * x + b * y); return; } } }值得提醒的是：这里a * x + b * y理论上应该等于g，但中间乘积可能溢出int。为了验证方便，可以先用小范围输入，或者把乘积强制转成long long再比较。
第三层，随机测试。用随机数生成器生成100万组大数，跑一遍性能测试，确认没有栈溢出和超时。这层测试能暴露迭代版和递归版在边界行为上的差异。
第四层，应用验证。拿一组已知答案的模逆元题来测，比如求3在模7下的逆元，正确答案是5，因为3 * 5 = 15 ≡ 1 (mod 7)。跑通了再去处理复杂场景。
4.4 比语法更重要的：理解递归中的"状态传递"
最后说一个我在带新人时反复强调的点：递归函数不是"黑盒"，你要想清楚每一层的职责。写扩展欧几里得的时候，递归返回的不只是gcd，还顺带返回了一组系数。这组系数对应的是"当前这一层的a、b的组合方式"。上一层的系数用完之后，这一层通过x = y1; y = x1 - (a/b)*y1把它"翻译"成上一层的组合方式。一层一层翻译回去，最终得到原始a、b的组合。
我在实际写代码时，喜欢在关键递归调用前后加注释，把每一层对应的等式写出来：
// 当前层：a * x + b * y = g // 递归层：b * x1 + (a % b) * y1 = g // 回溯后：x = y1, y = x1 - (a / b) * y1这样的注释对调试和理解都有很大帮助。等你亲手写完两遍，你会发现扩展欧几里得其实没那么神秘——它就是辗转相除法的副产品，只是在除法的过程中顺便记录了一路变化的系数。掌握了这一点，后面看RSA、看模逆元、看各种同余方程解法，都会顺畅很多。
我自己批代码的经验是：扩展欧几里得最大的坎不是数学，而是递归回溯那一步的变量名。如果你能把每一层的"角色"分清楚，错误率至少降低一半。下次如果你也被这段递归绕得头疼，不妨拿笔在纸上画一遍47和36的完整递归树，把每一层的a、b、x、y都标出来，你会有一种豁然开朗的感觉。
