★ FEATURED ARTICLE 一位做后端的朋友前阵子问我欧几里得算法辗转相除法的证明到底该怎么讲才通俗。他写了好几年代码gcd用得滚瓜烂熟分数化简、比例缩放、网格计算里到处是它的影子。但被人追问“为什么每次取模之后最大公约数不变”他发现自己只会背结论不会讲道理。我特别理解这个状态——多数工程师写过多年代码却没认真读过这个算法的证明。今天我想把它彻底讲透先从直觉上建立画面再给出六行的核心引理证明随后回答“算法为什么一定会停”最后把证明翻译成工程代码顺带引出扩展欧几里得和模逆元。整个阅读过程不需要任何高深数论基础刚学算法的新人也好想补短板的开发者也好都能跟得上。1. 先回答最容易被跳过的问题为什么取模之后答案还在1.1 算法在做什么欧几里得算法的核心只有一行关系gcd(a, b) gcd(b, a mod b)再加上一个终止条件gcd(a, 0) a。递归地看就是把(a, b)变成(b, a mod b)因为第二个参数变成余数后严格小于原来的除数所以问题规模在缩小。朴素去算最大公约数最直接的想法是同时枚举a和b的因子、找共同最大值或者先做质因数分解再取公共部分。相比之下欧几里得的方法根本不做因子分解只做带余除法靠等式把问题一步步缩小直到其中一个参数是 0。这里的关键在于新组合和旧组合的最大公约数必须相等否则每一步缩小都是在错的方向上暴走。要理解这个算法我觉得应该先把目标说清楚整个证明包含两个部分。第一引理成立也就是gcd(a, b) gcd(b, a mod b)第二算法能终止也就是余数序列不会无限循环。前者保证答案正确后者保证过程会停。这两个部分缺一不可。很多人只记实现、跳过证明后来一旦遇到错误样例或性能问题就完全无从下手根子就在这里。1.2 一个很有用的几何画面直觉往往是最先被忽略的部分。想象一个a×b的矩形其中b小于a。用边长b的正方形去铺这个矩形能铺floor(a/b)个完整行最后剩下一条宽度为r a mod b的窄矩形。现在问题变成找一个最大边长d使得这个矩形不管横向还是纵向都能被边长d的正方形铺满。欧几里得的核心观察是如果d能同时整除a和b那么整个大矩形能被d×d方块铺满再看剩余那条r×b的窄矩形它同样能被d×d方块铺满所以d也必须是b和r的公约数。反过来如果d能同时铺满b边和r边那把它们组合起来整个a×b矩形同样能铺满。也就是说大矩形的可铺性问题和剩余条带的可铺性问题完全等价。这个画面直观地解释了“为什么取模之后答案不变”多出来的部分就是用a除以b的余数表示的而两者可公度的“最大方块边长”被完整保留了下来。这个几何直觉也是我后面理解扩展欧几里得时的一个重要锚点。1.3 证明唯一需要的前置知识整个证明过程不需要任何高级数论工具唯一用到的性质是若d|a且d|b则对任意整数x, y都有d|(xa yb)。理由很简单如果a d×sb d×t那么xa yb d(xs yt)这当然是d的倍数。这是个非常初等的结论却恰好是整个欧几里得证明的引擎。记住这个性质后面的推导一行都不会卡。2. 核心引理公约数集合在每一步都不变2.1 把目标改写成集合语言先设r a mod b于是存在整数q使得a qb r且0 ≤ r b。要证明gcd(a, b) gcd(b, r)其实可以证一个更强的结论a与b的全体公约数集合和b与r的全体公约数集合完全一致。集合一样最大值自然一样最大公约数也就一样。这是一个非常漂亮的技巧。很多“相等”的证明与其在等式变换里绕来绕去不如直接去比较两边的公约数集合。凡是公约数类的问题优先想集合抽象基本不会走偏。我用记号D(a, b)表示所有同时整除a和b的正整数组成的集合。下面开始推两个方向的包含关系。2.2 两个方向的包含证明先证D(a, b) ⊆ D(b, r)。任取d ∈ D(a, b)由定义d整除a和b。因为r a - qbr是a和b的一个整数线性组合。根据前面那唯一的整除性质d一定整除r。于是d同时整除b和r也就是说d ∈ D(b, r)。再证D(b, r) ⊆ D(a, b)。任取d ∈ D(b, r)d整除b和r。因为a qb r这是b和r的一个整数线性组合所以d整除a。于是d ∈ D(a, b)。两个方向都成立集合相等。因此gcd(a, b) gcd(b, r)。整个推导不到六行却把这个算法的正确性核心钉死了不管取多少次模最大公约数都稳稳不变。顺带说一句这个证明还有一个副产品——用到线性性质的那两步已经暗含了“每一步的最大公约数都能表示成原始a、b的线性组合”这是后面扩展欧几里得出现的伏笔。2.3 用一道具体算式验证直觉空谈理论不如手算一遍。求gcd(252, 105)252 2×105 42 所以 gcd(252, 105) gcd(105, 42) 105 2×42 21 所以 gcd(105, 42) gcd(42, 21) 42 2×21 0 所以 gcd(42, 21) gcd(21, 0) 21每一步都用引理做了一次替换。最后一步的gcd(21, 0)等于 21因为 0 可以被任何正整数整除所以所有 21 的约数都是(21, 0)的公约数最大就是 21。从集合的角度来看D(21, 0)就是 21 的所有正约数最大值自然是 21。许多初学者对gcd(a, 0) a不太放心觉得“0 怎么会有约数呢”。这里其实不是在给 0 找约数而是在说“能同时整除 21 和 0 的最大的数”只要d整除 21那么0 d×0也必然成立约数条件自动满足。这层理解到位了终止条件也就顺理成章。2.4 一个常见的认知误区很多人第一次接触这个证明时会问为什么不直接看“每一步的商”为什么非要绕到集合上我的看法是商在这里没有数学义务。带余除法的商q只是用来构造r a - qb的真正的信息全在余数r里。换句话说q是步骤的副产品r才是状态的载体。如果陷入“商变大变小会怎么样”的思考容易把自己绕晕。记住一个口诀带余除法里商负责凑数余数负责携带公约数信息。这个角度对理解后面的扩展欧几里得尤其重要——到那时候商才开始出场作为回溯系数参与计算。3. 终止性不是显然的——余数为什么一定会归零3.1 严格递减是一种“硬承诺”引理保证了答案不变但如果算法一直跑下去不出结果那也没用。所以必须证明给定任意非负整数a, b反复执行(a, b) → (b, a mod b)最终一定会出现第二个参数为 0。设一开始b等于m。第一步生成的余数r1满足0 ≤ r1 b第二步的余数r2满足0 ≤ r2 r1第三步的余数r3满足0 ≤ r3 r2。因为每一步都要求“余数小于当前除数”非零余数严格递减。一个严格递减的非负整数序列长度不可能超过首项本身因此最多执行m次就会碰到余数为 0。这是利用了整数集的良序性质任何非空正整数集合都有最小元。直观地说余数序列像一架只能往下走、且每步至少下一级台阶的楼梯地板高度是固定的无论怎么设计套路走到地面的步数总是有限的。不要小看这一步很多递归算法看起来“收敛”实际上没有任何单调量在收缩跑着跑着就爆栈了。3.2 两步减半的复杂度直觉证明终止只是及格工程上还要问“大概要跑多久”。按最坏情况分析欧几里得算法的步数是对数级别。这里给一个我很喜欢的粗证明它比直接背复杂度结论有用得多。看连续两步设当前除数为n下一步余数为r1 n mod m再下一步余数为r2 m mod r1。如果r1 ≤ n/2相当于一步就把除数降到了n/2以下。如果r1 n/2那么因为r1比n的一半还大下一步的商必然是 1——2r1 nm mod r1不可能商出 2。于是r2 m - r1结合r1 n/2且m ≤ n可以推出r2 n/2。换句话说每两步至少把当前除数缩小一半。所以最多用2 × log2(min(a, b))步算法必然结束。这个推理没有用斐波那契那种精细的极值分析但工程上已经足够对 64 位整数log2不超过 64最坏步数一百出头完全不用担心。真正的极致最坏情形是相邻斐波那契数比如gcd(F(n), F(n-1))推导过程可以去翻数论教材这里不展开因为“两步减半”已经解释了为什么复杂度是对数级。3.3 终止条件下的边界情况终止条件gcd(a, 0) a表面简单细想有个细节如果两个参数都是 0 呢gcd(0, 0)按数学定义其实是比较尴尬的——全体整数都能同时整除 0 和 0不存在“最大”的正约数。不同教材和不同语言的处理不完全一样。工程上主流的做法是定义gcd(0, 0) 0比如 Python 标准库math.gcd(0, 0)返回 0。做自己的实现时我的建议是把这个边界情况在文档里写清楚免得下游逻辑对返回值产生误解。理解了“严格递减”和“0 的整除约定”之后递归和迭代实现都可以放心写了。4. 把证明翻译成代码递归、迭代与工程细节4.1 递归实现最忠实于证明的写法以下是最常见的递归实现def gcd_rec(a, b): if b 0: return a return gcd_rec(b, a % b)这段代码的结构和数学引理一一对应b为 0 就走终止条件否则把(b, a % b)作为新参数继续递归。由于前面的证明已经保证了参数会严格递减递归深度是可控的。需要提醒的是Python 的默认递归深度约 1000而欧几里得递归深度是对数级的正常场景不会溢出。但如果在实现时把参数写错方向比如不小心写成gcd_rec(a, a % b)余数序列就可能不递减跑着跑着就RecursionError了。4.2 迭代实现工程里我更常用的一种def gcd_iter(a, b): while b: a, b b, a % b return a迭代写法就是在手动模拟递归的过程。while b的含义是“只要第二个参数不是 0 就继续”循环体里的a, b b, a % b与递归的调用参数完全相同。有一个小细节值得说如果初始时a b第一次循环会自动完成交换。因为a b时a % b等于a于是(b, a % b)变成(b, a)相当于把两个数换了位置算法的正确性不受影响。这个实现没有栈开销性能上更稳。我在生产代码中几乎都用迭代版尤其在循环反复调用 gcd 的批处理场景里省下的函数调用开销是可感知的。4.3 负数、0 和跨语言余数的坑欧几里得证明从头到尾都假定参数是非负整数。一旦出现负数要小心不同语言的取模约定。C/C 的%是截断除法结果的符号和被除数相同比如-5 % 3在 C 里等于-2Python 的%是向下取模结果符号和除数一致比如-5 % 3等于1。同一个数学表达式在不同语言里结果不同如果直接把负数丢进自己写的欧几里得函数会产生奇怪的负余数序列。最稳妥的策略是在函数入口统一处理对a和b先取绝对值再进算法。这样既绕开了符号约定差异又能保证输出为非负最大公约数。另外再强调一次gcd(0, 0)的约定标准库一般返回 0自定义实现时要跟着对齐还应该写单元测试覆盖(0, 0)、(负数, 正数)、大数对数这几类用例。别觉得这些边界多余公钥算法里一个符号问题就能让整个加解密流程跑出匪夷所思的结果。4.4 gcd 的真实应用场景工程上最大的用途之一是分数化简一个分数p/q先算d gcd(p, q)然后把分子分母同除以d得到最简分数。所有涉及大整数的计算系统包括一些支付场景里的汇率换算都依赖这一步。另一个有意思的场景是网格坐标判断视线从(x1, y1)到(x2, y2)能经过多少个内部整数格点结果是gcd(|x2 - x1|, |y2 - y1|) - 1。这个公式在做战棋类游戏、网格路径分析时非常实用。再往后就是密码学模逆元、RSA 私钥选取全都建立在 gcd 等于 1 的判断和扩展欧几里得之上。可以说欧几里得算法是所有“找公约数”问题的地基。5. 证明带来的长尾收益从裴蜀定理到扩展欧几里得5.1 证明里悄悄藏着一个定理回看 2.2 的证明会发现一个容易被忽略的事实每一步的余数r都能写成当前a、b的整数线性组合即r a - qb。从第一步一路回溯最后的非零余数g gcd(a, b)也一定是原始两个数a、b的整数线性组合。也就是说存在整数x、y使得ax by g。这就是裴蜀定理的存在性版本。这个定理在密码学里出场率极高它能直接回答“某个模运算下到底存不存在逆元”。这里要小心一点裴蜀定理只保证“存在”不告诉你怎么找到x、y。真正用来求x、y的是扩展欧几里得算法。这个算法不是横空出世的新东西它只是把原始欧几里得过程的每一步商记录下来然后在递归返回时不断修正系数。5.2 扩展欧几里得的代码骨架def egcd(a, b): if b 0: return (a, 1, 0) g, x1, y1 egcd(b, a % b) x y1 y x1 - (a // b) * y1 return (g, x, y)解释一下返回值g是最大公约数x、y是满足a×x b×y g的系数。递归返回的关键动作在于已知b和r a mod b的线性组合系数(x1, y1)也就是g b×x1 r×y1把r a - (a//b)×b代进去得到g b×x1 (a - (a//b)×b)×y1整理成g a×y1 b×(x1 - (a//b)×y1)。所以新的系数就是代码里的x y1y x1 - (a//b)×y1。这个过程我反复手推过很多次每次写递归实现时默念一遍系数更新基本不会记错。5.3 模逆元从定理到实用求ax ≡ 1 (mod m)的x是密码学和数论里的常客。要保证解存在必要条件是gcd(a, m) 1。使用egcd(a, m)得到ax my 1在模m意义下my那一项消失所以解出来的x就是ax ≡ 1的解。这个x通常要调整到 0 到m-1之间对m取模即可。这时回头看看整个链条是从“公约数集合相等”的引理开始的。如果当初没有认真推那两步集合包含关系到了递归回溯阶段大概率只能背模板x1、y1到底谁乘谁非常容易写反。我自己见过不少同学在扩展欧几里得的系数更新上反复试错最后靠打印调试猜对底层的原理反而不清楚。但如果你已经能独立把 2.2 的集合证明写出来这个记忆负担就不存在了——不是背代码而是从证明中自然长出来的代码。5.4 什么时候该在这条路上继续深入如果只是做日常业务开发gcd 最简单的迭代实现已经足够。但如果你想搞密码学、解析数论或者单纯想把算法底子打牢扩展欧几里得是绕不开的一道坎。往后的路还有用扩展欧几里得解一次不定方程、在大整数模约简里做蒙哥马利约减、在处理椭圆曲线时频繁出现的模逆计算甚至 RSA 密钥生成中的私钥指数计算都是这条线上长出来的。我个人的学习顺序建议是先把原始欧几里得的引理证明吃透再手写扩展欧几里得并用随机数验证返代结果最后再看它被用进 RSA 的具体环节。一步一步来比直接看密码学教材的结论稳得多。写到最后分享一点个人体会。我在很长一段时间里都是“会用 gcd不信证明”的状态直到有一回调试一个扩展欧几里得实现卡了快一晚上最后把几个变量拆开仔细核对才意识到症结就是没理解r a - qb这个关系在递归回溯中如何传导。从那以后凡是涉及 gcd 的代码我都会先在心里过一遍公约数集合相等的两步推理整除a和b的d一定整除r整除b和r的d一定整除a。这个不到五行的证明是理解所有相关算法的总开关。如果你能把它独立写出来再去看扩展欧几里得、裴蜀定理和模逆元整个过程会顺畅非常多。下次再被人问起辗转相除法你也能从头从容地证起而不是说“就是这么定义的”。
阅读完成 · 觉得有帮助？
