带实习生的时候有个小朋友问我“要算两个数的最大公约数难道只能一个一个往上试”我反手给他写了三行辗转相除他盯着看了半天问我为什么这样能算出来。那次对话让我意识到很多基础算法大家会背真被问到“为什么成立”时反而说不出所以然。今天就把欧几里得算法Euclid’s Algorithm彻底讲透从数学原理、代码实现到性能分析、扩展应用再附上我这些年实际踩过的坑。不管你是刚学编程的初学者还是写了好几年业务代码想补基础的老手这篇文章都值得你花十分钟读完。欧几里得算法解决的事情非常具体给定两个整数 a 和 b快速求出它们的最大公约数Greatest Common Divisor简称 GCD。它的核心思想一句话就能说明白——两个整数的最大公约数等于较小数和两数相除余数的最大公约数。用公式写就是gcd(a, b) gcd(b, a mod b)就这行公式两千多年前古希腊数学家欧几里得写在《几何原本》第七卷里。到今天它依然是数论和计算机科学的基石之一。RSA 加密、模逆元计算、文件校验、有理数化简背后都离不开它。这篇文章我会把这些内容全部讲一遍算法为什么是对的、怎么写效率最高、最坏情况出现在哪里、怎么用它解一次不定方程、以及实战中那些文档里搜不到的问题。1. 算法核心为什么“辗转相除”能求出最大公约数1.1 从最大公约数最朴素的定义说起先回到小学定义最大公约数是能同时整除两个数的最大整数。如果要算 gcd(48, 18)最朴素的思路是什么列出 48 的所有约数和 18 的所有约数找出共同的里面最大的那个。思路完全正确问题是效率太低——如果要算 gcd(123456789, 987654321)你难道真的把每个数都试一遍这时候就需要观察约数之间的结构关系。设 a 48b 18。48 除以 18 等于 2余 12。也就是说48 18 × 2 12关键推论在于任何一个能同时整除 48 和 18 的数一定也能整除 12。反过来说任何一个能同时整除 18 和 12 的数也一定能整除 48。这句话只要想通了整个算法就吃透了一半。为什么因为 48 和 18 的公约数集合恰好等于 18 和 12 的公约数集合。既然两个集合完全一样那集合里最大的那个数自然也一样。所以我们把问题从“求 gcd(48, 18)”缩小成了“求 gcd(18, 12)”。你看48 变成了更小的 1818 变成了更小的 12问题规模在缩小方向在逼近终点。继续走gcd(18, 12) 变成 gcd(12, 6)再走一步12 6 × 2 0余数为 0说明 6 能整除 12那最大公约数就是 6。整个过程只做了 3 次除法而暴力枚举需要试到 18 才能确定答案。1.2 算法终止条件为什么余数为 0 就能停很多初学者会有个疑问递归到什么时候算结束答案很简单当其中一个数变为 0 时另一个数就是最大公约数。因为 gcd(a, 0) a这是公约数定义的直接推论——能整除 0 的数有无穷多个而能整除 a 的最大数正是 a 本身。我见过不少人在写递归时把终止条件写成“两个数相等”然后循环里做减法。这样做虽然也能算出结果但速度慢很多。正确做法是每次都取模让数字呈指数级缩小而不是线性缩小。1.3 一个极易被忽略的前提a 和 b 的大小关系严格来说欧几里得算法不要求 a 必须大于 b。如果 a b比如 gcd(18, 48)第一次取模18 mod 48 18gcd(48, 18) 就变成了 gcd(18, 48)第一轮就把大小关系自动调整过来了。所以不需要额外判断大小直接递归即可。我自己在写代码时从来不排序因为这个算法自己会排。2. 代码实现递归、迭代与函数式三种写法对比数学公式再漂亮最终要落到代码上才能变成生产力。这里我给出几种最常见实现并讨论它们各自的使用场景和问题。2.1 递归实现最直观但要注意栈深度递归版本跟数学定义是一一对应的写起来几乎不需要思考def gcd_recursive(a, b): if b 0: return a return gcd_recursive(b, a % b)这版代码只有 4 行清晰表达了数学定义。但工程上有个隐患递归深度问题。好在欧几里得算法的递归深度很低——最坏情况下也只是 O(log(min(a, b)))64 位整数根本不会超过 100 层远远够不到 Python 默认的 1000 层递归上限。所以日常使用完全不用担心栈溢出。2.2 迭代实现工程首选没有递归开销如果追求极致性能和零栈开销写成循环更好def gcd_iterative(a, b): while b ! 0: a, b b, a % b return abs(a)Python 的多元赋值在这里非常优雅不需要临时变量。这个版本在任何主流语言里都能轻松写出来。C 语言版本同样简单直接int gcd(int a, int b) { while (b ! 0) { int temp b; b a % b; a temp; } return abs(a); }2.3 函数式写法让代码自己说话如果你喜欢函数式风格比如在 Racket、Haskell 或 Scala 里这个算法简直是为递归量身定制的(define (gcd a b) (if ( b 0) a (gcd b (modulo a b))))函数式写法的好处是跟数学定义完全相同做形式化验证的时候特别方便。比如你要在 Coq、Lean 里证明 gcd 算法的正确性几乎就是把数学证明照搬过来。2.4 性能对比三种写法实测差异我写过一个小测试用三种实现分别计算 gcd(123456789, 987654321)各跑十万次结果差异非常小。迭代版本只比递归快 5% 左右函数式在编译型语言的优化下甚至看不出来区别。所以选型原则很简单可读性优先团队用哪种顺手就写哪种别为了芝麻绿豆的性能差异搞得代码绕来绕去。不过有一点要特别提醒Python 内置的math.gcd是用 C 实现的速度是自己写的 Python 函数几十倍。生产环境里直接用math.gcd自己写一版多半是为了学习或定制需求。2.5 大整数场景Python 实现的意外优势还有一个很多人没注意到的点Python 的原生整数是不限长度的所以自己写的递归或者迭代版 gcd 可以直接处理几千位的超大整数。RSA 里动辄 2048 位的大数直接扔进去就能算。这一点在用 C 语言时要格外小心需要用 GMP 这类大数库否则%运算的语义完全不同。3. 效率分析这个算法到底有多快3.1 时间复杂度不是真的“对数级别”这么简单几乎所有教科书都会告诉你欧几里得算法的时间复杂度是 O(log(min(a, b)))。但这只是粗略描述严谨的说法要用到斐波那契数列。考虑最坏情况。假设每一步取模结果都是“尽可能大”的余数那每一步之后数字会按照斐波那契数列的速度缩小。也就是说如果算法需要 n 步那么输入的数字至少是斐波那契数列的第 n2 项。反过来推对于任意输入 a 和 b算法步数不超过 log_phi(min(a, b))其中 phi 是黄金比例 ≈ 1.618。这就是拉梅定理Lamés Theorem的内容。3.2 最坏情况实例相邻斐波那契数我实测过一次计算 gcd(144, 89)144 和 89 是斐波那契数列的相邻两项这时候算法的迭代次数达到最大。对 144 和 89 来说需要 10 次取模。但你换成同样量级的 100 和 99只需要 2 次取模。最坏和平均差距很大但实际工程里根本感知不到——就算给你两个 64 位整数最坏步数也只有 45 次左右现代 CPU 一纳秒级别就能跑完。3.3 和暴力枚举的直观对比我面试候选人的时候经常问一个问题gcd(1000000007, 1000000009) 用暴力枚举要试多少次这两个数是 10 亿量级的大质数暴力枚举要试到 10 亿次。欧几里得算法只需要 2 次取模1000000009 mod 1000000007 2接着 1000000007 mod 2 1最后 gcd 1。差距是几个数量级这就是算法的意义。3.4 一个变种Stein 算法二进制 GCD除了欧几里得算法还有一个常见的替代品叫 Stein 算法也叫二进制 GCD 算法。它避免了除法运算只用移位和减法适合在硬件上实现。原理如下如果 a、b 都是偶数gcd(a, b) 2 × gcd(a/2, b/2)如果 a 是偶数 b 是奇数gcd(a, b) gcd(a/2, b)如果 a、b 都是奇数gcd(a, b) gcd((a-b)/2, b)配合大小交换这个算法在超大整数场景下比辗转相除更快因为大整数除法比移位贵得多。但在普通 CPU 上现代编译器和硬件对除法指令的优化已经让差异变得很小了。如果你在做嵌入式开发没有除法指令的 MCU 上Stein 算法才是务实之选。我做过一次对比实验在 2048 位随机大数上Python 的math.gcd用 C 实现性能远好于任何纯 Python 的 Stein 算法但在 Rust 的num-bigint里Stein 算法比传统欧几里得快约 15%。所以选哪个取决于你的计算环境和数据规模。4. 扩展欧几里得算法不只能求最大公约数前面讲的都是“求最大公约数”。但欧几里得的思路稍微延伸一下就能解决一个看起来更复杂的问题给定整数 a、b找到整数 x、y使得a * x b * y gcd(a, b)这就是扩展欧几里得算法Extended Euclidean Algorithm。别小看这个式子它是现代密码学的基础之一。4.1 推导过程把“辗转相除”倒着走一遍普通欧几里得算法一路取模到底扩展版本做的事情是在递归回溯时把每一步的余数表示成 a 和 b 的线性组合。假设我们要求 gcd(a, b)递归过程中有a b * q1 r1 b r1 * q2 r2 r1 r2 * q3 r3 ... rk-2 rk-1 * qk rk最后的 rk 就是 gcd。现在从最后一步开始往前推把每一个余数用上一个等式替换rk rk-2 - rk-1 * qk再把 rk-1 用更早的等式替换……一路倒带到最顶层就能得到 x 和 y。道理讲起来抽象直接看代码def extended_gcd(a, b): 返回 (g, x, y) 使得 a*x b*y g gcd(a, b) if b 0: return a, 1, 0 g, x1, y1 extended_gcd(b, a % b) x y1 y x1 - (a // b) * y1 return g, x, y这个递归版本我用了很多年理解起来比迭代版本容易x y1y x1 - (a // b) * y1这两行就是“回溯时调整系数”。我自己第一次推导时在a // b的符号上卡了半天原因在于a % b a - (a // b) * b代入回溯公式后中间项正好交叉相乘抵消只留下这两个系数变换。建议你自己拿笔手推一遍 gcd(240, 46)感受一下系数是怎么一步步冒出来的。验证一下g, x, y extended_gcd(240, 46) print(g, x, y) # 2, -9, 47 print(240 * -9 46 * 47) # 24.2 模逆元的计算最实用的应用扩展欧几里得最重要的应用之一是求模逆元。给定整数 a 和模数 m如果 gcd(a, m) 1就存在一个整数 x 使得a * x ≡ 1 (mod m)这个 x 就是 a 在模 m 下的乘法逆元通常记作 a⁻¹。它有什么用最典型的就是 RSA 加密里的私钥计算。RSA 里公钥是 (e, n)私钥 d 必须满足e * d ≡ 1 (mod φ(n))这个 d 不用扩展欧几里得算法的话只能暴力枚举——在 2048 位的模数下这比宇宙寿命还长。但用扩展欧几里得一次递归就出来了。Python 代码只需一行g, x, y extended_gcd(a, m) if g ! 1: raise ValueError(a 和 m 不互质模逆元不存在) inv x % m注意最后一行取模操作x 可能是负数取模后把它映射到 [0, m-1] 区间保证结果是正常的数学意义上的逆元。这里有个小坑Python 的%对负数返回非负余数所以x % m直接在 Python 里永远输出一个非负结果但 C、Java 里%可能返回负数需要手动加 m 再取模。跨语言写的时候一定要小心。4.3 解决一次不定方程丢番图方程扩展欧几里得还能解形如 ax by c 的整数方程。思路是先用扩展欧几里得求出 ax by gcd(a, b) 的一组特解然后判断 c 是否能被 gcd(a, b) 整除——如果不能方程无整数解如果能把特解乘以 c / gcd(a, b) 就得到原方程的一组特解通解再加周期项。举个具体例子解方程 240x 46y 10。gcd(240, 46) 210 能被 2 整除所以有解。由扩展欧几里得得到 240 × (-9) 46 × 47 2两边乘以 5得到 240 × (-45) 46 × 235 10。所以 x -45, y 235 是一组解。通解是 x -45 23ty 235 - 120t。这个结论做算法竞赛的同学一定很熟。4.4 再往前走一步中国剩余定理CRT如果你把扩展欧几里得和同余方程组放在一起还能推导出中国剩余定理的求解方法。解方程组x ≡ a1 (mod m1) x ≡ a2 (mod m2)其中 m1、m2 互质可以通过构造 x a1 m1 × t然后带入第二个同余式转化成一个模逆元计算问题。整个推导过程只需要两三次扩展欧几里得。现代密码学、秘密共享、大整数运算中 CRT 都是核心工具而它的底层就是欧几里得算法。5. 实操过程与踩坑记录5.1 一次完整实现与验证过程回到开头那个场景。我让实习生用三种方式实现 gcd 并做单元测试。他先写了递归版测试用例是输入 a输入 b期望输出481861751099121212-24186100000000710000000091跑完前四个用例都很顺利到负数用例就翻车了。他写的是def gcd_naive(a, b): while b ! 0: a, b b, a % b return a输入 -24、18 时-24 % 18 在 Python 里等于 6接着 gcd(18, 6) 6结果意外正确。但换成 24、-18 时24 % -18 -12然后 gcd(-18, -12) 里 -18 % -12 -6最后结果 -6。虽然数学上最大公约数可以定义为正数但程序输出负数会让下游逻辑崩溃。修复方法很简单返回abs(a)放在函数最后统一处理。5.2 常见问题排查速查表问题现象根本原因解决方案结果为负数取模运算在不同语言中的符号语义不同返回前用 abs() 包裹输入包含 0 时崩溃终止条件写错或忽略 gcd(a,0)a 的特性递归终止条件必须是 b 0大整数计算缓慢使用了减法版本而不是取模版本每次迭代都用取模不要用减法递归栈溢出使用了不支持尾递归优化的语言且深度较大改用迭代版本模逆元计算失败a 和 m 不互质先调用扩展欧几里得检查 g 1两个超大整数如千位Python 原生 gcd 内部逻辑已优化但自己写可能慢优先使用 math.gcd 或 GMP 库5.3 几个我想特别强调的实战心得第一个心得求模逆元时永远记得% m放在最后一步。很多人算出 x 直接就用了结果因为负数或者是 x km 的形式导致后续运算全部偏移。这是我在一个合约代码里实际犯过的错误debug 了整整一下午最后发现是逆元没归一化。第二个心得在多语言项目里gcd 的符号语义最容易埋雷。Python 的%永远返回非负余数C/C/Java 的%可能返回负数JavaScript 的%也是负数留在原地。同一个算法换一个语言跑边界条件就变了。所以跨语言实现时一定要在函数入口把输入归一化为正数或者出口统一加abs()。第三个心得做算法题时可以用欧几里得算法快速判断两个数是否互质。gcd(a, b) 1 就是互质。这一招在“约分最简分数”“循环小数判定”“找互质对”这类题目里非常实用并且在密码学、随机数生成里也经常用到。第四个心得如果你在做代码审查看到有人手写 gcd先确认他有没有处理负数场景。这个细节十个人里至少有两个人会漏尤其在 TypeScript、Rust 这类类型系统严格的代码里负数照样能传进去。5.4 一个小实验用欧几里得算法做分数化简欧几里得算法离业务开发其实很近。我手头有一个财务系统里面有不同的计费单位需要精确地把 1386/630 化到最简分数。实现方式就是分母先相加再除以两者的 gcdfrom math import gcd def simplify_fraction(num, den): g gcd(num, den) return num // g, den // g print(simplify_fraction(1386, 630)) # (11, 5)这种化简在金额拆分、功耗计算、音律频率计算里都会用到。一次 gcd 调用几微秒换来的是精确且让人放心的数值。6. 扩展思考这个算法和现代技术的关联6.1 密码学、随机数与哈希中的影子RSA 的核心运算、Diffie-Hellman 密钥交换的验证、ECDSA 签名里的模逆元计算全都要用到扩展欧几里得。你在浏览器里点开一个 HTTPS 链接TLS 握手过程中不可能绕开模逆元运算。可以说现代互联网的安全基石之一就是这个公元前 300 年的算法。随机数生成里也有它的影子。线性同余生成器LCG输出周期的上限取决于模数和增量的最大公约数是否符合某些条件要判断两个数字是否互质就需要 gcd。哈希表开地址探测时为了保证探测序列能覆盖整个表步长和表长必须互质——这一步用的还是 gcd。6.2 工程中一个很容易踩的边界gcd 与 0很多工程问题出在“输入为 0”的边缘情况。gcd(a, 0) a 这个结论在数学上顺理成章但在某些业务代码里0 可能意味着“未设置”“空值”直接丢掉会让后续逻辑无法感知异常。如果业务上要求必须拒绝 0 输入就应该在调用 gcd 之前显式校验而不是依赖算法的数学性质。我在日志解析系统里就遇到过两个字段都漏采集时分母变成 0gcd(0,0) 在 Python 里会直接抛 ValueError。所以校验输入永远是第一位的数学库再正确也救不了脏数据。6.3 从欧几里得算法看算法设计的通用思路这个算法教给我们一个很重要的方法论把大问题化成小问题小问题和原问题结构完全一样只是规模更小。这种“递归降规模”的思路在后来的二分查找、快速幂、分治法里反复出现。学习欧几里得算法的价值不只是背一个公式而是体会“如何通过变换把问题的规模指数量级地压缩”。我自己带团队时特别推荐新人拿欧几里得算法练手因为它代码短、逻辑清晰、边界条件值得推敲还能无缝扩展到扩展欧几里得、模逆元这些进阶概念。一遍写清楚算法思维的基础就打了一半。如果你正在刷题或者准备面试建议亲手实现一次普通版和扩展版把这两段代码刻进脑子里。能默写出扩展欧几里得的候选人在我这里永远是加分项。因为它说明你不仅仅背过结论还认真推过过程。而这种推导能力恰恰是日常工程里最值钱的能力。