輾轉相除法

在数学中，辗转相除法，又称欧几里得算法（英语：Euclidean algorithm），是求最大公约数的算法。辗转相除法首次出现于欧几里得的《几何原本》（第VII卷，命题i和ii）中，而在中国则可以追溯至东汉出现的《九章算术》。
两个整数的最大公约数是能够同时整除它们的最大的正整数。辗转相除法基于如下原理：两个整数的最大公约数等于其中较小的数和两数的差的最大公约数。例如，252和105的最大公约数是21（）；因为252 − 105 = 21 × (12 − 5) = 147
，所以147和105的最大公约数也是21。在这个过程中，较大的数缩小了，所以继续进行同样的计算可以不断缩小这两个数直至其中一个变成零。这时，所剩下的还没有变成零的数就是两数的最大公约数。由辗转相除法也可以推出，两数的最大公约数可以用两数的整数倍相加来表示，如21 = 5 × 105 + (−2) × 252
。这个重要的结论叫做裴蜀定理。 
辗转相除法最早出现在欧几里得的《几何原本》中（大约公元前300年），所以它是现行的算法中历史最悠久的。这个算法原先只用来处理自然数和几何长度（相当于正实数），但在19世纪，辗转相除法被推广至其他类型的数学对象，如高斯整数和一元多项式。由此，引申出欧几里得整环等等的一些现代抽象代数概念。后来，辗转相除法又扩展至其他数学领域，如纽结理论和多元多项式。
辗转相除法有很多应用，它甚至可以用来生成全世界不同文化中的传统音乐节奏。在现代密码学方面，它是RSA算法（一种在电子商务中广泛使用的公钥加密算法）的重要部分。它还被用来解丢番图方程，比如寻找满足中国剩余定理的数，或者求有限域中元素的逆。辗转相除法还可以用来构造连分数，在施图姆定理和一些整数分解算法中也有应用。辗转相除法是现代数论中的基本工具。
辗转相除法处理大数时非常高效，如果用除法而不是减法实现，它需要的步骤不会超过较小数的位数（十进制下）的五倍。拉梅于1844年证明了这点，同时这也标志着计算复杂性理论的开端。

归纳、递归和无穷递降

下文的论证会用到三种相关的数学方法，分别是数学归纳法、递归和无穷递降。数学归纳法经常用来证明某个定理对所有自然数成立：首先证明定理对一个特定的数n₀成立（通常是1）；然后证明如果定理对自然数n成立的话，那么它对自然数n + 1成立。这样，便可证明定理对所有大于n₀的自然数也成立。递归是将相关的数组成一个数列(a₁, a₂, a₃...)，当中除初始项外，其中每一项都用前一项或前几项表示。如斐波那契数列就是递归的，每一项Fₙ都等于Fₙ−1 + Fₙ−2（n≧2）。辗转相除法中的一些等式也是递归的。最后，无穷递降是用方程的一个自然数解导出比它小的自然数解。但是，这种转化不能永远进行下去，因为只有有限个小于原来的自然数解的自然数。所以，要么方程无解，不然在有限步内必然能得出最小的自然数解。在下文会用到此法来证明辗转相除法一定会在有限步内结束。

图形演示

辗转相除法的计算过程可以用图形演示。假设我们要在a×b的矩形地面上铺正方形瓷砖，并且正好铺满，其中a大于b。我们先尝试用b×b的瓷砖，但是留下了r₀×b的部分，其中r₀<b。我们接着尝试用r₀×r₀的正方形瓷砖铺，又留下了r₁×r₀的部分，然后再使用r₁×r₁的正方形铺……直到全部铺满为止，即到某步时正方形刚好覆盖剩余的面积为止。此时用到的最小的正方形的边长就是原来矩形的两条边长的最大公约数。在图中，最小的正方形面积是21×21（红色），而原先的矩形（绿色）边长是1071×462，所以21是1071和462的最大公约数。

计算机实现

辗转相除法可用伪代码表示，比如除法版本可以写成
function gcd(a, b)
    while b ≠ 0
        t ← b
        b ← a mod b
        a ← t
    return a

c++版本：
 1 int gcd(int m,int n) 2 { 3         int t = 1; 4         while(t != 0) 5         { 6                 t=m%n; 7                 m=n; 8                 n=t; 9         }10         return m;11 }

Python3版本：
1 def gcd(a, b):2     while b != 0:3         t = a % b4         a = b5         b = t6     return a
在第k次循环开始时，变量b的值是前一次运算的余数rₖ−1，变量a的值是再前一次运算的余数rₖ−2。步骤
b := a mod b的作用等同于递归式rₖ ≡ rₖ−2 mod rₖ−1。变量t的功能是在下一个余数rₖ计算过程中临时性地保存rₖ−1的值。在一次循环结束时，变量b的值是前一次运算的余数rₖ，变量a的值是再前一次运算的余数rₖ−1。
在欧几里得定义的减法版本，取余运算被减法替换。
function gcd(a, b)
    if a = 0
       return b
    while b ≠ 0
        if a > b
           a ← a − b
        else
           b ← b − a
    return a
变量a和b的值分别是前两次的余数rₖ−1和rₖ−2。假定第k次循环开始时a大于b，那么a等于rₖ−2，因为rₖ−2 > rₖ−1。在循环过程中，a重复减去b直到比b小，此时a就是下一个余数rₖ；然后b重复减去a直到比a小，此时b就是下一个余数rₖ₊₁；重复执行直到b = 0。
以下是递归版本：
function gcd(a, b)
    if b = 0
       return a
    else
       return gcd(b, a mod b)

c++递归版本如下：
1 int gcd(int n,int m)2 {3         if(m==0)4                 return n;5         else6                 return gcd(m,n%m);7 }

Python3版本：
1 def gcd(a, b):2     if b == 0:3         return a4     else:5         return gcd(b, a % b)
例如GCD(1071, 462)的计算过程是：函数的第一次调用计算GCD(462, 1071 mod 462) = GCD(462, 147)；下一次调用计算GCD(147, 462 mod 147) = GCD(147, 21)，在接下来是GCD(21, 147 mod 21) = GCD(21, 0) = 21。

整数分解算法

计算最大公约数是很多整数分解算法的重要步骤，如Pollard's rho算法、Shor算法、Dixon分解法以及Lenstra椭圆曲线分解。用辗转相除法算最大公约数效率非常高。而连分数分解法由于用到了连分数，所以也需要使用辗转相除法。

算法效率

辗转相除法的计算效率已经被彻底研究过了。一个算法的效率可以用计算所需步数乘以每步计算的开销表示。加百利·拉梅于1884年指出，用辗转相除法计算两个数的最大公约数所需的步数不会超过其中较小数十进制下的位数h的5倍。因为每一步的计算开销通常也是h数量级的，所以辗转相除法的复杂度是h²。

最差情况

假设用辗转相除法求自然数a和b（a > b > 0）的最大公约数需要N步，那么满足这一条件的a和b的最小值分别是斐波那契数FN₊₂和FN₊₁。这可以用数学归纳法证明。假设N = 1，b整除a，满足这一条件的a和b最小是b = 1、a = 2，正是F₂和F₃。现在假设这一规律对M − 1有效。一个需要M步的算法的第一步是a = q₀b + r₀，第二步是b = q₁r₀ + r₁。因为算法是递归的，它需要M − 1 步才能算出GCD(b, r₀)，其中b和r₀的最小值是FM₊₁ 和 FM。所以a的最小值是当q₀ = 1 的时候，此时a = b + r₀ = FM₊₁ + FM = FM₊₂。1844年，加百利·拉梅发现这个证明标志着计算复杂性理论的诞生。这也是斐波那契数列的第一个实际应用。
这个结果也证明了辗转相除法的运算步骤不会超过较小数十进制下的位数的五倍。因为如果算法需要N步，那么b一定大于或等于FN₊₁，也就是一定大于或等于φᴺ⁻¹，其中φ是黄金分割比。因为b ≥ φᴺ⁻¹，所以N − 1 ≤ logφb。因为log₁₀φ > 1/5，(N − 1)/5 < log₁₀φ logφb = log₁₀b，所以N ≤ 5 log₁₀b。所以，辗转相除法不会进行超过O(h)次除法，其中h是较小数b在十进制下的位数。

其他算法的效率

因为辗转相除法的高效率，它在实践中被广泛使用。作为对比，本段中介绍以下辗转相除法以外的其他最大公约数算法的效率。
计算两数a和b的最大公约数有一个效率很慢的算法：将a除以从2到b之间的每一个整数以计算出它们所有的公约数，其中最大的一个即是最大公约数。在这个算法中，步骤数随b线性增长，也就是随输入数字的位数呈指数级增长。另一个很低效的算法是计算出两个数的所有素因数（见上文），最大公约数等于所有公共素因数的乘积。但是整数分解算法效率极低，很多现代的加密系统甚至依靠这种低效率来防止资料被破解。
除了辗转相除法之外，也有一些高效的算法存在，如二进制最大公约数算法将除法操作替换成了二进制的移位，以进一步提高用计算机运算时的效率。但是，这种改变并没有降低算法的复杂度（仍然是O(h²)），虽然它在计算机上确实比辗转相除法快些。也可以通过只检视a和b的前几位数来进一步提高效率，不过效果并不明显。二进制版的算法还可以扩展到其它进制，效率最多可以提升五倍。
对于超过25,000位数的大数，有一种改进使算法复杂度降低至平方级以下，如Schönhage、Stehlé、Zimmermann等人提出的算法。这些算法利用2×2的矩阵（见上文）。这些亚平方级的算法复杂度通常是O(h (log h)² (log log h))。

其他数系

如上文所述，辗转相除法最早用来寻找两自然数的最大公约数，但其实它也可以被推广至实数，甚至是多项式、二次整数和赫尔维茨四元数。在这些数系中，辗转相除法甚至被用来证明一个重要特性：惟一分解，即这些数系中的数能够被惟一地分解成不可约元素（素数在这些数系的对应物）。惟一分解是数论中很多证明的基础。

欧几里得整环

如果一个支持两种二元运算（+ 和 ·）的元素的集合形成一个交换环R并且可以使用辗转相除法求最大公约数，那么这个集合叫做欧几里得整环。这两个二元运算不必是平常算数中的加法和乘法，它们可以是更广泛的概念，如群或幺半群中的运算。但是这些运算仍然需要遵守交换律、结合律、分配律。
推广之后的辗转相除法需要一个欧几里得函数，即一个将R映射到非负整数集合的函数f，使得对于R中非零元素a和b，R中存在q和r满足
a = qb + r，
f(r) < f(b)
。例如上文中用于高斯整数的范数函数。这个函数f可以是数的绝对值或模，也可以是多项式的次数，只要辗转相除法计算过程中它的值不断减小就行，这样算法便能在有限步内结束。这非常依赖于非负整数的良序性，即每个非空的非负整数集合都有一个最小数。
任何欧几里得整环都满足算数基本定理：欧几里得整环中的数可以惟一分解。所以任何欧几里得整环都是惟一分解整环，但反之不然。欧几里得整环是GCD整环（任意两元素都存在最大公约数的整环）的子类。也就是说，在某些整环中，两元素存在最大公约数但却不能用辗转相除法计算。欧几里得整环都是主理想环，即其中每一个理想都是主理想，但并不是每个主理想环都是欧几里得整环。
欧几里得整环的惟一分解性质在很多场合都非常有用。例如，高斯整数的惟一分解性质可以方便地导出勾股数的公式，或者证明费马平方和定理。惟一分解性质也是加百利·拉梅于1847年基于约瑟夫·刘维尔的建议发表的证明费马最后定理的尝试中的关键部分。拉梅的尝试需要形如x + ωy的数的惟一分解性质，其中x和y是整数，ω = e²ⁱπ/ⁿ是1的n次方根，即ωⁿ = 1。虽然这对于某些n成立（如n=3时的艾森斯坦整数），但在其他情况下并非总是正确的。惟一分解性质在分圆域的失效使恩斯特·库默尔发明了理想数的概念，随后理查德·戴德金创造了理想的概念。