查看“︁辗转相除法”︁的源代码

[[分类:整除理论]]
[[分类:数论算法]]
[[分类:以 Euclid 命名]]
{{InfoBox
|name=欧几里得算法
|eng_name=Euclidean algorithm
|aliases=辗转相除法,Euclid's algorithm
}}
'''辗转相除法'''或'''<ins>欧几里得</ins>算法'''('''Euclidean algorithm''')，指对两个[[整数]]，通过对其不断互相做[[带余除法]]得到其[[最大公因数]]的算法。

== 定理 ==

=== 算法 ===

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

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

=== 终止条件 ===

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

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

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

=== 最大公因数不变 ===

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

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

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

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

=== 伪代码 ===

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

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

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

返回 rₖ₋₁
</syntaxhighlight>


{{整除与质数}}