辗转相除法

欧几里得算法
术语名称	欧几里得算法
英语名称	Euclidean algorithm
别名	Euclid's algorithm

辗转相除法或欧几里得算法(Euclidean algorithm)，指对两个整数，通过对其不断互相做带余除法得到其最大公因数的算法。

定理

算法

对整数 [math]\displaystyle{ a, b }[/math] ，其中 [math]\displaystyle{ b\neq 0 }[/math] 且 [math]\displaystyle{ b\not\mid a }[/math] ，记 [math]\displaystyle{ r_0=a, r_1=b }[/math] ，则存在以下 [math]\displaystyle{ k+1 }[/math] 个等式：

[math]\displaystyle{ \begin{align} r_0 = q_0 r_1 + r_2 &, 0 \leq r_2 \lt |r_1| \\ r_1 = q_1 r_2 + r_3 &, 0 \leq r_3 \lt r_2 \\ \dots\\ r_{k-1} = q_{k-1} r_k + r_{k+1} &, 0 \leq r_{k+1} \lt r_k \\ r_k = q_k r_{k+1} + 0 \end{align} }[/math]

终止条件

对数 [math]\displaystyle{ a, b }[/math] ，做带余除法 [math]\displaystyle{ a = b q + r, 0 \leq r \lt |b| }[/math] ，则 [math]\displaystyle{ \operatorname{gcd}(a, b) = \operatorname{gcd}(b, r) }[/math] 。且 [math]\displaystyle{ r \leq |b| }[/math] 。所以 [math]\displaystyle{ |b| \gt r_2 \gt r_3 \gt \dots }[/math] 是递减的自然数列。

算法不强制带余除法中的余数为最小非负余数，只需要保证递减。若为绝对最小余数 [math]\displaystyle{ a = bq + r, -\left\lfloor \tfrac{|b|}{2} \right\rfloor \lt r \leq \left\lfloor \tfrac{|b|}{2} \right\rfloor }[/math] ，则 [math]\displaystyle{ \operatorname{gcd}(a, b) = \operatorname{gcd}(b, r) = \operatorname{gcd}(b, |r|)\ }[/math] 且 [math]\displaystyle{ |r| \leq \frac{|b|}{2} }[/math] 。所以 [math]\displaystyle{ |b| \gt |r_2| \gt |r_3| \gt \dots }[/math] 是递减的自然数列。

因此，余数（或余数的绝对值）总是构成了一个递减的序列，会有一个递减到 0 为止。

最大公因数不变

由于 [math]\displaystyle{ \operatorname{gcd}(a, b) = \operatorname{gcd}(b, r) }[/math] ，在这个算法过程中，一定有

[math]\displaystyle{ \operatorname{gcd}(r_0, r_1) = \operatorname{gcd}(r_1, r_2) = \operatorname{gcd}(r_2, r_3) = \dots = \operatorname{gcd}(r_k, r_{k+1}) = \operatorname{gcd}(r_{k+1}, 0) = r_{k+1} }[/math]

因此，序列最后一个不是 0 的数就是两个数的最大公因数。

算法

原理

对整数 [math]\displaystyle{ a,b }[/math] ，记 [math]\displaystyle{ r_0 = |a|, r_1 = |b| }[/math] ，不断用较大数对较小数取余，并用结果替代较大数，即 [math]\displaystyle{ r_{k+1} = r_{k-1} - r_{k} q }[/math] 。直到某个 [math]\displaystyle{ r_{m+1} = 0 }[/math] ，此时较小数 [math]\displaystyle{ r_m }[/math] 即是两个数的公约数。

由于上述定理中，较大数对较小数运算得到余数时，除数、余数及以后所有余数，其绝对值一定会变小，构成一个严格递减数列。同时自然数上从给定数开始不存在无穷下降链，必然有限次内减小到 0 ，余数绝对值序列必然会在有限次内减小到 0 。

实际人工计算时，使用绝对值并取绝对最小余数的带余除法可以更快收敛。 对计算机而言，硬件实现一般进行的是无符号数的取余，有符号数会通过处理成无符号数计算， 因此通常会将两数绝对值后进行基于普通的（最小非负余数的）带余除法的辗转相除法，此外有一些对大数的优化算法。

伪代码

过程 欧几里得算法
别名 euclidean_algorithm
参数 a, b : 整数 // 被求最大公因数的两个数
返回 : 自然数 // 最大公因数

令 r₀ ← |a| // 自然数
令 r₁ ← |b| // 自然数

循环 k ← 1
当 rₖ ≠ 0 时
执行
    记 rₖ₊₁ ← rₖ mod rₖ₋₁
继续循环 k ← k + 1

返回 rₖ₋₁

整除理论
整除关系	整除、倍数、因数	带余除法
正整数的分类	1、质数、合数
	质数测试	试除法、埃氏筛、线性筛
最大公约数理论	公倍数、最小公倍数 [math]\displaystyle{ \operatorname{lcm} }[/math]、公因数、最大公因数 [math]\displaystyle{ \operatorname{gcd} }[/math]	辗转相除法
	互质
算术基本定理	算术基本定理	标准质因数分解