辗转相除法

定义

辗转相除法处理的是两个整数的最大公约数，也就是两数共有的约数中最大的那一个，通常记作 gcd(a, b) 或 (a, b)^[1]。当两个数的公约数只有 1 时，称二者互素，此时算法给出的结果就是 1^[1]。

算法的输入是两个正整数 a 与 b，一般约定 a 大于 b。先做一次带余除法，求出 a 除以 b 的余数 r；如果余数不为零，就进入下一轮，原来的除数变成被除数，原来的余数变成除数，再求一次余数；一旦某一步的余数等于零，这一轮的除数就是两者的最大公约数^[2]。

把每一轮写成等式，即 r 下标 k 减 2 等于商 q 下标 k 乘以 r 下标 k 减 1 再加上余数 r 下标 k，其中余数总要小于上一轮的除数，如此循环直到某个余数等于 0 为止，最后一个非零余数便是最大公约数^[1][3]。这个递推关系也可以简写成 $\gcd(a,b)=\gcd(b,\ a\bmod b)$，反复代入直到第二个参数为 0^[1]。

原理

算法成立的关键在于两对数的公约数集合相同。若某个整数同时整除 a 与 b，它也必然整除 a 减去 b 的若干倍所得到的余数；反过来，若某数同时整除 b 与余数，它同样整除 a，所以 a 与 b 的公约数和 b 与余数的公约数完全一致，最大公约数自然不变^[3]。

算法一定会结束：每做一次带余除法，余数都比上一轮的除数小，于是得到一个严格递减的非负整数序列，而这样的序列不可能无限延续，因此若干步之后必然出现余数 0^[3]。每一轮的计算量主要花在求商上，余数可以由被除数减去商与除数的乘积得到^[4]。

以 1071 与 462 为例：1071 = 2 × 462 + 147，462 = 3 × 147 + 21，147 = 7 × 21 + 0，最后的非零余数为 21，所以两者的最大公约数是 21^[1]。

这一过程也有几何解释：设想一个边长为 a 与 b 的长方形，每次用边长等于当前较短边的正方形去填充，剩下的部分再重复同样的做法，直到恰好铺满为止，最后所用正方形的边长就是 a 与 b 的最大公约数^[1][5]。

整个算法的循环结构可以用下面的流程表示：

graph TD

A[输入 a 和 b] --> B{b 是否为零}

B -- 否 --> C[计算 a 除以 b 的余数 r]

C --> D[a 改为 b，b 改为 r]

D --> B

B -- 是 --> E[输出 a]

发展历程

公元前 300 年前后，欧几里得把这一算法写在几何原本第七卷的命题 1 与命题 2 中^[6][1]。学者大多认为它并非欧几里得本人的发现，方法可能更早约 200 年就已出现，最早采取的应当是不带除法的减法形式，欧多克索斯或许已经掌握^[6]。

中国一侧的记载见于九章算术。该书约成书于公元前 2 世纪至公元 1 世纪，其方田章提出更相减损术，用“以少减多”的反复相减求出两数的“等数”，也就是最大公约数，其原理与辗转相除法在数学本质上相通^[7][2]。

1844 年，法国数学家拉梅（Gabriel Lamé）证明了该算法在最坏情况下所需除法次数的上界，指出步数最多出现在输入为相邻两项斐波那契数的时候，这一结论被视为计算复杂性理论的开端，也是斐波那契数列最早的实际应用^[4]。其后又有更精细的估计出现，例如所需步骤不超过较小数十进制位数的 5 倍^[8]。

从 19 世纪起，这一算法被推广到高斯整数、一元多项式等对象，由此产生了欧几里得整环一类抽象代数概念；后来它又进入纽结理论、多元多项式等方向^[9]。

应用

最常见的用途是约分。把一个分数化成最简形式，需要反复求分子与分母的最大公约数；计算机代数系统在处理分数运算后，也以这一步作为收尾^[7]。

在密码学中，辗转相除法是 RSA加密算法的重要组成部分，也用于求有限域中元素的逆元^[9]。它的扩展形式除了最大公约数之外，还能给出满足贝祖等式的整数系数，即把最大公约数写成两个原数的整数倍之和^[10]。

算法还被用来解丢番图方程、寻找满足中国剩余定理的数，以及构造连分数；在施图姆定理和一些整数分解算法中同样有它的身影^[9]。多项式情形的算法用于构造施图姆链，进而服务于控制理论中的劳斯–赫尔维茨判据^[4]。

在数学之外，它甚至可以用来生成不同文化中的传统音乐节奏^[9]。在程序设计与算法竞赛中，求最大公约数也是处理数论问题时的常备工具^[11]。

局限

算法的每一轮都要做一次除法或取模，而这正是主要的计算开销所在；在计算机上处理大整数时，除法的代价明显高于加减与移位运算^[11][4]。

若改用减法实现，当两数相差悬殊、商的数值很大时会明显变慢，因为一次整数除法相当于商的那么多次减法^[4]。针对这一点出现了若干改进算法：二进制最大公约数算法用移位和减法取代除法，莱默算法只取两数的高位数字来估计商，以减少大数除法的次数^[4]。

当输入的位数很多时，算法的总代价大约与位数的平方成正比；分数超过约 25000 位的大整数，通常改用准线性时间的算法来处理^[4]。

把算法推广到实数之后，有限步终止不再有保证：如果两个实数之比是无理数，相除过程会一直进行下去^[4]。此外，它只给出最大公约数，本身并不提供两个数的质因数分解^[4]。

参见

• 最大公约数 —— 辗转相除法所要计算的量。

• 更相减损术 —— 《九章算术》中只用减法求最大公约数的方法，与本词条原理相通。

• 扩展欧几里得算法 —— 在求最大公约数的同时给出贝祖等式整数系数的推广。

• 连分数 —— 辗转相除过程中得到的商构成实数的连分数展开。

• 多项式 —— 辗转相除法可推广到一元多项式，用于求最大公因式。

• RSA加密算法 —— 现代公钥密码学中依赖本算法的重要应用。