辗转相除

定义

辗转相除要解决的问题是求两个正整数的最大公约数，即能够同时整除这两个数的最大正整数。^[2] 以 $\gcd(a,b)$ 表示 $a$ 与 $b$ 的最大公约数；当 $\gcd(a,b)=1$ 时，称这两个数互质。^[2] 最大公约数无法用一个统一公式直接给出，只能借助算法逐步算出。^[4]

算法的执行步骤为：先求出 $a$ 除以 $b$ 所得的余数 $r$；若 $r=0$，则 $b$ 就是最大公约数；若 $r\neq 0$，则以原有的除数 $b$ 作为新的被除数、以余数 $r$ 作为新的除数，重复同样的运算，直至余数为 0，此时最后一步的除数即为答案。^[5] 这一关系可简写成 $\gcd(a,b)=\gcd(b,\,a\bmod b)$。^[6]

原理

算法成立的依据是一条基本性质：若整数 $a$、$b$、$r$ 满足 $a=qb+r$（$q$ 为整数），则 $a$ 与 $b$ 的最大公约数等于 $b$ 与 $r$ 的最大公约数。^[5] 也就是说，每一步都把原先的数对换成更小的一对，而两者的公约数集合完全一致，最大公约数因此保持不变。^[7]

以计算 1071 与 462 的最大公约数为例：$1071=2\times462+147$，$462=3\times147+21$，$147=7\times21+0$。^[2] 最后一步余数为 0，故所求得的最大公约数是 21。^[2]

算法一定会停下来：每一步得到的余数都小于上一步的除数，余数构成一个严格递减的非负整数序列，其中必然出现 0。^[7] 可以证明，求 $\gcd(a,b)$（$a>b>0$）所需的除法次数不超过 $2\log_2 a$。^[5]

计算流程可表示为：

flowchart LR

A[输入 a, b] --> B[计算 r = a mod b]

B --> C{r = 0}

C -- 否 --> D[a 取 b, b 取 r]

D --> B

C -- 是 --> E[输出 b]

发展历程

辗转相除法最早出现在几何原本中，该书约成书于公元前 300 年，相关记载见于第七卷命题 i 和 ii。^[8] 不过学界普遍认为这未必是欧几里得本人的发现，该方法可能在其之前约 200 年就已被知晓，至少减法的形式是这样，并被认为为欧多克索斯（约公元前 375 年）所熟悉。^[8]

中国古代的九章算术载有“更相减损术”，做法与之相近：不断以大数减小数，直到两数相等，所得“等数”就是最大公约数。^[9] 当时计数使用算筹，只用减法的操作在筹式上更为方便。^[9]

该算法起初只处理自然数与几何长度；到 19 世纪，它被推广到高斯整数、一元多项式等对象，并由此发展出欧几里得整环等抽象代数概念。^[1] 1844 年，法国数学家拉梅（Gabriel Lamé）给出了所需除法次数的上界，这一结果被视为计算复杂性理论的开端。^[10]

应用

在现代密码学中，辗转相除法是 RSA算法的重要组成部分，而 RSA 是电子商务等领域广泛使用的公钥加密算法。^[1]

该算法还用于求解丢番图方程、寻找满足中国剩余定理的整数，以及求有限域中元素的逆。^[1] 通过扩展欧几里得算法，可以求出使 $ax+by=\gcd(a,b)$ 成立的整数 $x$、$y$。^[3]

辗转相除法可以用来构造连分数，在施图姆定理和一些整数分解算法中同样有应用。^[1] 它甚至能用于生成不同文化传统音乐中的节奏型。^[1]

局限

该算法需要反复做取模（除法）运算，对高精度大整数来说除法取模开销较大，此时可改用只做减法的更相减损术，或改用借助位运算优化的 Stein算法。^[6] 但更相减损术的运算次数明显更多，在极端情形下（如 100 与 1）需要上百次减法。^[6]

拉梅定理给的是上界而非精确值：所需除法次数不超过较小数十进制位数的 5 倍，实际步数通常远低于该上界，例如计算 326 与 78 时理论上界为 10 步，实际只需 5 步。^[10] 作为该定理的推论，当 $a>b$ 时算法使用的除法次数为 $O(\log b)$。^[11]

参见

• 最大公约数 —— 辗转相除法所要求出的对象。

• 最小公倍数 —— 可由最大公约数与两数乘积的关系间接求得。

• 欧几里得 —— 在《几何原本》中记载该算法的古希腊数学家。

• 几何原本 —— 辗转相除法现存最早的文献出处。

• 九章算术 —— 记载与辗转相除法相近的更相减损术的中国古代数学著作。

• RSA算法 —— 以辗转相除法为重要组成部分的公钥加密算法。