背景

最大公约数

欧几里得的辗转相除法计算的是两个自然数a和b的最大公约数g，意思是能够同时整除a和b的自然数中最大的一个。两个数的最大公约数通常写成GCD(a, b)，或者简写成(a, b)，但是第二种写法也被使用在其他数学概念，如二维向量的坐标。

如果GCD(a, b) = 1，则称a和b互素。a和b是否互素和它们是否素数无关。如，6和35都不是素数，因为它们都可以分解为多于一个素因数的乘积：6 = 2 × 3，35 = 5 × 7。但是，6和35互素，因为除了1以外没有自然数同时整除6和35。

令g = GCD(a, b)。由于a和b都是g的整数倍，所以可以写成a = mg、b = ng，并且不存在更大的整数G > g使等式成立。为了使g尽可能大，就要使a和b中所有公约数都提取出来归入g中，所以自然数m和n一定互素，并且a和b的最大公约数g可以被a和b的所有其他公因数c整除。

我们可以用右图来解释最大公约数的概念：设一个长方形的边长为a和b。因为a和b的任何公约数c都可以整除a和b，所以长方形的边都可以等分为长度为c的线段，也就是长方形可以被边长为c的正方形正好填满。而最大公约数g是所有可能的c中最大的一个。例如，一个24 × 60的长方形区域可以分成1 × 1、2 × 2、3 × 3、6 × 6或12 × 12的正方形网格。也就是说，12是24和60的最大公约数。

a和b的最大公约数是两数共有的素因数的乘积。例如，462可以分解成2 × 3 × 7 × 11；1071可以分解成3 × 3 × 7 × 17。462和1071的最大公约数等于它们共有的素因数的乘积3 × 7 = 21。如果两数没有公共的素因数，那么它们的最大公约数是1，也即这两个数互素。辗转相除法的优点就在于它能以有系统的方式求出两数的最大公约数，而无需分别对它们作因式分解。大数的素因数分解被认为是一个困难的问题，即使是现代的计算机也非常难于处理，所以许多加密系统的原理都是建基于此。

在数学中，尤其是高等数学的环论中，最大公约数有一个更加巧妙的定义：a和b的最大公约数g是a和b的线性和中的最小正整数，即所有形如ua + vb（其中u和v是整数）的数中的最小正整数。可以证明，所有ua + vb都是g的整数倍（ua + vb = mg，其中m是整数）。用现代数学语言来说，a和b生成的理想即是由g生成的主理想。最大公约数的这个定义和其他定义的等价性将在下面描述。

三个数的最大公约数的定义和两个数的相同，即是它们共有的素因数的积，它们或者也可以按下式计算：

所以，欧几里得的辗转相除法实际可以计算任意多整数的最大公约数。

归纳、递归和无穷递降

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

算法描述

计算过程

辗转相除法是一种递归算法，每一步计算的输出值就是下一步计算时的输入值。设k表示步骤数（从0开始计数），算法的计算过程如下。

每一步的输入是都是前两次计算的非负余数rk−1和rk−2。因为每一步计算出的余数都在不断减小，所以，rk−1小于rk−2。在第k步中，算法计算出满足以下等式的商qk和余数rk：

其中0 ≤ rk rk−1。也就是rk−2要不断减去rk−1直到比rk−1小。

为求简明，以下只说明如何求两个非负整数a和b的最大公约数（负数的情况是简单的）。在第一步计算时（k = 0），设r−2和r−1分别等于a和b，第2步（此时k = 1）时计算r−1（即b）和r0（第一步计算产生的余数）相除产生的商和余数，以此类推。整个算法可以用如下等式表示：

如果有a b，算法的第一步实际上会把两个数字交换，因为这时a除以b所得的商q0会等于0，余数r0则等于a。然后，算法的第二步便是把b除以a，再计算所得之商和余数。所以，对于k ≥ 0总有rk<rk−1，即运算的每一步中得出的余数一定小于上一步计算的余数。

由于每一步的余数都在减小并且不为负数，必然存在第N步时rN等于0，使算法终止，rN−1就是a和b的最大公约数。其中N不可能无穷大，因为在r0和0之间只有有限个自然数。

正确性的证明

辗转相除法的正确性可以分成两步来证明。在第一步，我们会证明算法的最终结果rN−1同时整除a和b。因为它是一个公约数，所以必然小于或者等于最大公约数g。在第二步，我们证明g能整除rN−1。所以g一定小于或等于rN−1。两个不等式只在rN−1 = g是同时成立。具体证明如下：

证明rN−1同时整除a和b：因为余数rN是0，rN−1能够整除rN−2：rN−2 = qNrN−1因为rN−1能够整除rN−2，所以也能够整除rN−3：rN−3 = qN−1rN−2 + rN−1同理可证rN−1可以整除所有之前步骤的余数，包括a和b，即rN−1是a和b的公约数，rN−1 ≤ g。

证明最大公约数g能整除rN-1：根据定义，a和b可以写成g的倍数：a = mg、b = ng，其中m和n是自然数。因为r0 = a − q0b = mg − q0ng = (m − q0n)g，所以g整除r0。同理可证g整除每个余数r1, r2, ..., rN-1。因为最大公约数g整除rN−1，因而g ≤ rN−1。

因为第一步的证明告诉我们rN−1 ≤ g，所以g = rN−1。即：

举例

例如，计算a = 1071和b = 462的最大公约数的过程如下：从1071中不断减去462直到小于462（可以减2次，即商q0 = 2），余数是147：

然后从462中不断减去147直到小于147（可以减3次，即q1 = 3），余数是21：

再从147中不断减去21直到小于21（可以减7次，即q2 = 7），没有余数：

此时，余数是0，所以1071和462的最大公约数是21，这和用素因数分解得出的结果相同（见上文）用表格表示如下：

图形演示

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

计算商和余数

在每个步骤k中，辗转相除法都需要计算两个数rk−1和rk−2的商qk和余数rk：

其中0 ≤ rk rk−1。除法的算法保证这样的商和余数总是存在。自然数的除法算法还指出这样的商和余数是惟一的，但这对辗转相除法而言并非必要。

在欧几里得最初的描述中，商和余数是通过连续的减法来计算的，即从rk−2中不断减去rk−1直到小于rk−1。一个更高效的做法是使用整数除法和模除来计算商和余数：

计算机实现

辗转相除法可用伪代码表示，比如除法版本可以写成

在第k次循环开始时，变量b的值是前一次运算的余数rk−1，变量a的值是再前一次运算的余数rk−2。步骤b := a mod b的作用等同于递归式rk ≡ rk−2 mod rk−1。变量t的功能是在下一个余数rk计算过程中临时性地保存rk−1的值。在一次循环结丛时，变量b的值是前一次运算的余数rk，变量a的值是再前一次运算的余数rk−1。

在欧几里得定义的减法版本，取余运算被减法替换。

变量a和b的值分别是前两次的余数rk−1和rk−2。假定第k次循环开始时a大于b，那么a等于rk−2，因为rk−2 > rk−1。在循环过程中，a重复减去b直到比b小，此时a就是下一个余数rk；然后b重复减去a直到比a小，此时b就是下一个余数rk+1；重复执行直到b = 0。

以下是递归版本：

例如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。

使用绝对值最小的余数

在另一个版本的算法中，每一步还要把取余运算时计算出的商增加一后再重新计算余数（此时计算出的余数应该是负的），然后取两个余数的绝对值较小的数作为下一步运算时使用的余数。取余运算后，设rk是计算出的余数（此时为正），q是计算出的商：

即假设rk−1 > rk > 0。然后使用以下式子计算出一个负的余数ek：

如果|ek| rk|，那么用ek替换rk进行下一次运算。如利奥波德·克罗内克所指出的，这个版本需要的运算步骤是欧几里得算法的所有版本中最少的。

历史发展

辗转相除法是目前仍然在使用的历史最悠久的算法之一。它首次出现于《几何原本》（卷7命题1–2、卷10命题2–3）（大约公元前300年）。在卷7中用于整数，在卷10中用于线段的长度（以现代的观点看，线段的长度可视为正实数，也就是说辗转相除法实际可用于实数上，但是当时未有实数的概念）。卷10现的算法是几何的，两段线段a和b的最大公约数是a和b的公度中的最大值。

这个算法可能并非欧几里得发明，因为他也有将先前其他数学家的一些成果编进他的《几何原本》。数学家、历史学家范德瓦尔登（英语：Bartel Leendert van der Waerden）认为卷7的内容可能来自毕达哥拉斯学院出身的数学家写的关于数论的教科书。辗转相除法在当时很可能已为尤得塞斯（大约公元前375年）所知 ，甚至可能更早之前就已经存在，因为欧几里得和亚里士多德的著作中都出现了ἀνθυφαίρεσις一词（意为“辗转相减”）。

几个世纪之后，辗转相除法又分别被中国人和印度人独立发现，主要用来解天文学中用到的丢番图方程以及制定准确的历法。5世纪末，印度数学家、天文学家阿里亚哈塔曾称辗转相除法为“粉碎机”，这可能是因为它在解丢番图方程时很有效。在中国，《九章算术》中提到了一种类似辗转相减法的“更相减损术”。《孙子算经》中则出现了中国剩余定理的一个特例，但是直到1247年秦九韶才于其《数学九章》中解答了该定理的一般情况，当中用到了他发明的大衍求一术。此法的其中一部分实际上便是辗转相除的原理，秦九韶在书中对此有明确表述。在欧洲，辗转相除法首次出现于克劳德·巴希特（英语：Claude Gaspard Bachet de Méziriac）的著作《愉悦讨喜的问题》（Problèmes plaisants et délectables）的第二版在欧洲，辗转相除法被用于丢番图方程和构建连分数。后来，英国数学家桑德森（英语：Nicholas Saunderson）在其著作中收编了扩展欧几里得算法，作为一个有效计算连分数的方法。他将此法的来源归名于罗杰·科茨（英语：Roger Cotes）。

19世纪，辗转相除法促成了新数系的建立，如高斯整数和艾森斯坦整数。1815年，高斯用辗转相除法证明高斯整数的分解是惟一的，尽管他的研究到了1832年才首度发表。高斯在他的《算数研究》（出版于1801年）中实际上也有援引这个算法，但仅是以连分数方法的形式叙述。约翰·狄利克雷是第一个将辗转相除法作为数论的基础的数学家。狄利克雷提出，数论中的很多结论，如分解的惟一性，在任何使辗转相除法适用的数系中均有效。狄利克雷的数论讲义后来经理查德·戴德金编辑和推广，戴德金也有以辗转相除法来研究代数整数。比如，他是第一个用高斯整数的分解惟一性证明费马平方和定理的数学家。戴德金还率先定义了欧几里得整环的概念。19世纪末，戴德金所定义的理想概念使得数论的重心不必建基于辗转相除法，从而促进了理论的发展。

辗转相除法的其他应用发展于19世纪。1829年，施图姆将辗转相除法用于施图姆序列（用于确定多项式的不同实根的个数的方法）。

辗转相除法是历史上第一个整数关系算法（英语：integer relation algorithm），即寻找两个可通约实数的整数关系的算法。近年来，出现了一些新颖的整数关系算法，如埃拉曼·弗格森（英语：Helaman Ferguson）和福尔卡德于1979年发表的弗格森-福尔卡德算法（Ferguson–Forcade algorithm） 、以及与它相关的LLL算法（英语：Lenstra–Lenstra–Lovász lattice basis reduction algorithm）、HJLS算法以及PSLQ算法。

1969年，科尔（Cole）和戴维（Davie）基于辗转相除法创造了一种二人游戏，叫做“欧几里得游戏”。这个游戏有最优策略。游戏开始于两列分别为a和b个棋子组成的序列，玩家轮流从较长一列中取走较短一列棋子数量的m倍的棋子。如果两列棋子p和q分别由x和y个棋子组成，其中x大于y，那么玩家可以将序列p的棋子数量减少为自然数x − my。最后率先将一列棋子清空的玩家胜出。

数学上的应用

贝祖等式

贝祖等式说明，两个数a和b的最大公约数g可以表示为a和b的线性和。也就是说，存在整数s和t使g = sa + tb。

整数s和t可以从辗转相除法算出的商q0、q1……计算出。 从辗转相除法的最后一步开始，g可以表示成前一步的商qN−1和前两步的余数rN−2和rN−3：

而前两步的余数又分别可以表示成它们前两步的余数和商：

将这两行式子先后代入第一个式子，可以将g表示成rN−4和rN−5的线性和。重复进行迭代直到出现a和b：

最终，g可以表示成a和b的线性和：g = sa + tb。贝祖等式以及以上证明都可以扩展至欧几里得整环。

主理想和相关问题

贝祖等式提供了另一种定义a和b的最大公约数g的方法。考虑形如ua + vb（其中u和v是整数）的数的集合。因为a和b都可以被g整除，所以这个集合中的所有元素都可以被g整除。也就是说这个集合中的数都可以表示成g的倍数，或者a和b的其他公约数的倍数。但是，只有最大公约数才是这个集合的元素。根据贝祖等式，有g = sa + tb。换言之，当u = s、v = t时得出g。任何其他的公约数都不是这个集合的元素，因为它们都不能被比它们大的g整除。相反地，g的任何倍数都属于这个集合，只要令u = ms、v = mt，便有：

所以，形如ua + vb的数的集合等于g的整数倍的集合。也就是说，任意两个数的线性和的集合等同于它们最大公约数的整数倍的集合。a和b的最大公约数叫做a和b的理想的生成元素。这个最大公约数的定义导出了两个现代抽象代数的概念：主理想（由单个元素生成的理想）以及主理想整环（其每一理想都是主理想的整环）。

这个结果可以解决某些实际问题。例如，考虑两个容积分别为a和b的量杯，其中a和b为正整数。通过加入或倒去u倍第一个量杯的体积以及v倍第二个量杯的体积的液体，任何体积为ua + vb的液体都可以被量出（只要ua + vb为正数）。根据贝祖等式，凡是可以被量出的液体，其体积一定是a和b的最大公约数g的倍数。

扩展欧几里得算法

贝祖等式的整数s和t可以通过扩展欧几里得算法算出。这个扩展算法在原有辗转相除法的基础上增加了两个递归等式：

算法开始时：

加上这两个递归式后，当算法终止于rN = 0，贝祖等式的整数s和t分别由sN和tN给出。

这个算法的正确性可以用数学归纳法来证明。假设递归至第k−1步是正确的，也就是假设：

在j小于k时皆成立。则第k步运算得出以下等式：

因为rk−2和rk−1被假定是正确的，所以可以用s和t表示：

整理后得到第k步的结果，和我们期望得到的结果一致：

矩阵法

整数s和t也可以用矩阵运算得出。辗转相除法的计算过程：

可以写作2×2的商矩阵乘以一个2维余数向量：

令M表示所有商矩阵的乘积：

这使辗转相除法化简为：

如要用a和b的线性和表示g，可将等式两边同时乘以矩阵M的逆矩阵。M的行列式等于(−1)，因为它等于商矩阵的行列式的乘积，而每一个的行列式都是−1。因为M的行列式不为零，最终的余数向量可以利用M的逆矩阵解出：

由上式可以得出g = (−1) ( m22a − m12b)。

贝祖等式中的两个整数分别是s = (−1)m22、t = (−1)m12。矩阵法的效率可前文描述的辗转相除法的递归算法是相同的，每一步都有两次乘法和两次加法。

欧几里得引理和唯一分解

贝祖等式对辗转相除法的很多应用都很重要，如证明自然数的唯一分解性质假设数字L可以写成两个因数u和v的乘积，即L = uv。如果另一个数w与u互素的数也能整除L，那么w必须整除v，证明如下：如果u和w的最大公约数是1，则根据贝祖等式存在s和t使

两边都乘以v：

因为w整除等式右边，所以也应整除等式左边的v。这个结果叫做欧几里得引理。如果一个素数整除L那么它至少整除L的一个因数。如果一个数w互素于数列a1、a2、…、an 中的每一个数，则w也一定互素于它们的乘积a1 × a2 × … × an。

欧几里得引理足以证明每一个自然数的素数分解是惟一的。我们用反证法来证明，假设L可以分别分解成m个素数和n个素数，即：

根据假设，每个素数p都能整除L，因此它必须能够整除某个q；因为q也是一个素数，所以p = q。同理，对于每一个p都存在一个q与它相等。所以两种分解除了顺序不同以外是完全相同的。整数分解的惟一性在数学证明中有很多应用，下文将会提到。

线性丢番图方程

丢番图方程是以亚历山大数学家丢番图的名字命名的一类方程，它的解被限制在整数范围。关于整数x和y的线性丢番图方程形如：

其中a、b、c是已知整数。这个方程可以写成关于x的同余式：

令g为a和b的最大公约数，ax + by能够被g整除。所以，c一定能够被g整除，不然方程就无解。方程两边若同时除以 c g {\displaystyle {\tfrac {c}{g}}} ，方程就变成了贝祖等式：

其中s和t可以用扩展欧几里得算法求解。所以这个丢番图方程的一个解即是：

总体而言，丢番图方程如果有解，就一定有无数个解。只需要考虑两个解 (x1, y1) 和 (x2, y2)：

或者可以写成：

所以相邻两个解的x之间的差是 b g {\displaystyle {\tfrac {b}{g}}} ，y之间的差是 a g {\displaystyle {\tfrac {a}{g}}} 。这样，所有的解都可以表示成：

当t取遍所有整数时，方程所有的解都可以从 (x1, y1) 计算出来。如果限制为正整数解 (x > 0, y > 0) 的话，那么解的数量就可能是有限的。有时候，这种对解的限制使丢番图方程在未知数个数比方程数更多的情况下仍然能有唯一解，而在允许实数解的线性方程组中，这种情况是不可能的。

乘法逆和RSA算法

有限域是一个支持四种运算的数集。这四种运算也通称为加法、减法、乘法、除法，跟一般的四则运算有相同的性质，如交换律、结合律和分配律。举例来说，使用同余可以让13个数字的集合 {0, 1, 2, …, 12} 构成一个有限域。在这个域中，任何数算（加减乘除）都归约成13的模，例如 5 × 7 = 35 mod 13 = 9。对于任意素数p，都可以定义这种有限域；使用更复杂的方法，也可以对素数p的m次方定义这样的有限域。有限域也叫做伽罗瓦域，其缩写为 GF(p) 或 GF(p)。

在这样一个有m个数的域中，任何非零元素a都存在惟一乘法逆a 使aa = aa ≡ 1 mod m。这可以通过解同余式ax ≡ 1 mod m 得出，或者也可以解与之等价的丢番图方程

这个方程可用扩展欧几里得算法解出（参见上文）。在RSA算法中，寻找乘法逆是非常重要的一步，它决定了使用哪个数来解密信息。虽然RSA算法不使用域而是使用环，扩展欧几里得算法仍然可以用来求乘法逆。欧几里得算法也被应用于纠错码，例如，它可以代替Berlekamp–Massey算法解基于有限域的BCH码和里德-所罗门码。

中国剩余定理

辗转相除法也可以用来解线性丢番图方程组。如在中国剩余定理中，整数可以表示成被N个互素的数mi除留下的余数：

为了从x的N个余数xi中确定x的值，我们将这些式子组合成单个线性丢番图方程，其中模数M是所有模数mi的乘积，然后定义Mi如下：

也就是，Mi是除了mi以外所有模数的乘积。接着是关键的一步，寻找N个数hi使：

有了这些数hi之后，整数x可以用下式从余数xi中解出：

因为hi是Mi的乘法逆，所以可以使用扩展欧几里得算法求出（见上一节）。

连分数

辗转相除法和连分数有着紧密的关系。计算连分数的过程如下：

其中每个式子的右边最后一项都等于下一个式子的左边项的倒数。所以前两个式子可以组合成：

第三个式子可以代入分母中的r1/r0：

每一步中，最后一项rk/rk−1都可以用下一个式子代换，直至最后一个式子，结果是：

在上文的例子中计算了GCD(1071, 462)，其中商qk分别是2、3、7，所以分数 1071/462 可以写成如下连分数形式：

整数分解算法

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

算法效率

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

计算步数

计算两个自然数a和b的最大公约数所需的步数可以表示为T(a, b)。如果a和b的最大公约数是g，a = mg，b = ng，而m和n是两个互素整数，那么：

这可以通过在辗转相除法的计算过程中的每一步都除以g来证明。同样，当a和b同时乘以w时，计算步数不变：T(a, b) = T(wa, wb)。所以，对于数值上相近的数，如T(a, b)和T(a, b + 1)，计算步数可能相差很大。

根据辗转相除法的递归性质可以得出另一个公式：

其中，根据定义有T(x, 0) = 0。

最差情况

假设用辗转相除法求自然数a和b（a > b > 0）的最大公约数需要N步，那么满足这一条件的a和b的最小值分别是斐波那契数FN+2和FN+1。这可以用数学归纳法证明。假设N = 1，b整除a，满足这一条件的a和b最小是b = 1、a = 2，正是F2和F3。现在假设这一规律对M − 1有效。一个需要M步的算法的第一步是a = q0b + r0，第二步是b = q1r0 + r1。因为算法是递归的，它需要M − 1 步才能算出 GCD(b, r0)，其中b和r0的最小值是 FM+1 和 FM。所以a的最小值是当 q0 = 1 的时候，此时 a = b + r0 = FM+1 + FM = FM+2。1844年，加百利·拉梅发现这计算复杂性理论算复杂性理论的诞生。这也是斐波那契数列的第一个实际应用。

这个结果也证明了辗转相除法的运算步骤不会超过较小数十进制下的位数的五倍。因为如果算法需要N步，那么b一定大于或等于FN+1，也就是一定大于或等于φ，其中φ是黄金分割比。因为b ≥ φ，所以N − 1 ≤ logφb。因为log10φ > 1/5，(N − 1)/5 10φ logφb = log10b，所以N ≤ 5 log10b。所以，辗转相除法不会进行超过O(h)次除法，其中h是较小数b在十进制下的位数。

平均情况

辗转相除法的平均步骤数有三种不同的定义。第一种定义是计算已知自然数a和从0到a − 1范围内随机选取的自然数b的最大公约数所需的时间T(a)：

但是因为T(a, b)在连续整数间变化非常剧烈，所以T(a)的值也会显得很杂乱。

为了解决这个问题，第二种定义规定τ(a)只要取遍其中所有和a互素的数即可：

在小于a的数中，有φ(a)个数与a互素，其中φ是欧拉函数。在这个定义中，τ(a)的函数值增长得平稳很多。

误差项的增长率为O(a)，其中ε是无穷小量。公式中的常数C等于：

其中γ是欧拉-马歇罗尼常数，ζ′是黎曼ζ函数的导数。公式最左边的 12 π π --> 2 ln ⁡ ⁡ --> 2 {\displaystyle {\frac {12}{\pi ^{2}}}\ln 2} 由两个独立的方法确定。

因为第一种定义可以通过用第二种定义的求和来完成：

所以也可以由以下公式近似：

其中Λ(d)是冯·曼戈尔特函数。

第三种定义Y(n)定义为从1到n间随机选取a和b（均匀分布）时计算它们的最大公约数所需的平均步骤数：

将T(a)的近似公式代入，得到Y(n)的近似：

每一步的计算开销

在辗转相除法的每一步中，商qk和余数rk都通过rk−2和rk−1求出：

所以每一步的计算开销主要与计算商qk的算法有关，因为余数rk可以很迅速地从rk−2、rk−1和qk计算出来：

而计算一个h位整数的除法的算法复杂度是O(h(ℓ+1))，其中ℓ是商的位数。

作为对比，辗转相除法原先的版本使用的是减法，因此效率要慢很多。进行一次除法等同于进行q次减法（其中q是商）。如果a和b的比很大，计算出的商也很大，也就需要进行很多次减法。但在另一方面，计算出来的商在大多数情况下都是非常小的，除法中得出一个确定的商q的概率大约是 log 2 ⁡ ⁡ --> ( u u − − --> 1 ) {\displaystyle \log _{2}\left({\tfrac {u}{u-1}}\right)} 。其中u = (q + 1)。比如，商是1、2、3、4的可能性分别是大约41.5%、17.0%、9.3%、5.9%。因为计算机计算减法要快于除法，特别是对于很大的数字，所以减法版本的辗转相除法的性能可以比得上除法版本。这也被运用于二进制最大公约数算法。

综合考虑算法需要的步数和每一步的计算开销，辗转相除法随两个数字a和b的平均位数成平方级的速度增长(h)。设h0、h1、…、hN−1表示计算过程中的余数r0、r1、…、rN−1的位数，因为算法的步数N随h线性增长，所以算法的运算时间为：

其他算法的效率

因为辗转相除法的高效率，它在实践中被广泛使用。作为对比，本段中介绍以下辗转相除法以外的其他最大公约数算法的效率。

计算两数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))。

其他数系

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

有理数和实数

辗转相除法可以被应用至实数，如欧几里得在几何原本第10卷中所说的那样。算法的目的是计算出实数g，使已知实数a和b是它的整数倍：a = mg、b = ng，其中m和n是整数。这也就找到了a和b的整数关系，即找到整数s和t使sa + tb = 0。欧几里得使用辗转相除法来处理不可通约的长度。

实数的辗转相除法和整数的算法有两个区别。第一，余数rk是实数，虽然商qk仍然是整数。第二，算法不能保证在有限步内结丛。如果能在有限步内结丛，那么分数a/b是一个有理数，即：

于是我们可以写出它的有限连分数形式：[q0; q1, q2, …, qN]。如果算法无法结丛，那么a/b是无理数，可以写成无限的连分数形式：[q0; q1, q2, …]。无限连分数的一个例子是：黄金分割比φ = [1; 1, 1, …]和2的算术平方根：√2 = [1; 2, 2, …]。通常，算法能够结丛的可能性是很低的，因为对于实数a和b，几乎所有a/b都是无理数。

如果算法不结丛，也可以在第k步时终止计算，得到近似连分数[q0; q1, q2, …, qk]。终止时的k越大，则近似越准确。连分数m/n的分子和分母互素并满足下式：

其中递归的初始值是m−1 = n−2 = 1，m−2 = n−1 = 0。mk/nk是a/b在分母是nk的数中最精确的有理数近似值：

多项式

只含有一个变量x的多项式可以和整数一样进行加法、乘法和分解为不可约多项式（也就是多项式中的“素数”）。两个多项式a(x)和b(x)的最大公约数g(x)定义为它们分解之后共有的不可约因式的乘积，这可以用辗转相除法进行计算。对于多项式的算法和整数的算法很相似，在每个步骤k，计算出满足以下递归式的商多项式qk(x)和余数多项式rk(x)：

其中r−2(x) = a(x)，r−1(x) = b(x)。所选择的商式必须能使qk(x) rk−1(x)的首项系数和rk−2(x)的相等，这样才能保证每个余数的次数小于前一个余数（deg[rk(x)] < deg[rk−1(x)]）。因为非零多项式的次数是非负整数，并且在每一步都减小，所以辗转相除法的计算一定能在有限步内结丛。最后一个非零余数即是两个多项式a(x)和b(x)的最大公约数。

例如，有如下两个四次多项式，都可以分解成两个二次多项式的乘积：

和

a(x)除以b(x)得到余数：

在下一步中，b(x)除以r0(x)得到r1(x) = x + x + 2。最终，r0(x)除以r1(x)得到的余数为0，所以r1(x)是a(x)和b(x)的最大公约数，这和它们因式分解的结果相符合。

上文所述的很多应用也适用于多项式。辗转相除法可以解多项式的线性丢番图方程和中国剩余定理，也可以用来定义多项式的连分数展开式。

多项式的辗转相除法也有其他应用，如施图姆定理，一个用于计算多项式在给定区间内的实根个数的方法。这被应用于其他领域，如控制论的劳斯-赫尔维茨稳定性判据。

最后，多项式的系数不必局限于整数、实数、甚至复数。这些系数可以是其他域中的元素，如上文所述的有限域GF(p)。从辗转相除法得出的结论也可以直接推广至这类多项式。

高斯整数

高斯整数是满足α = u + vi的复数，其中u和v是普通整数，i是虚数单位（-1的平方根）。通过在高斯整数中定义辗转相除法，根据上文贝祖等式可以证明高斯整数的惟一分解。高斯整数的惟一分解性质在很多应用中都很重要，如计算勾股数或者证明费马平方和定理。辗转相除法用于这些应用很方便，但并非必不可少，一些定理也可以由其他方式证明。

对于两个高斯整数α和β的辗转相除法和普通整数只有两个区别。像整数一样，算法的第k步计算出商qk和余数rk：

其中rk−2 = α，rk−1 = β，每个余数都严格地小于前一个余数，|rk| rk−1|。第一个区别即是：商和余数都是高斯整数，也就是复数，所以商qk是透过对实际比例（如复数α/β）的实部和虚部取最近似整数来找出的。第二个区别就是需要定义复数比较大小的方法。所以我们定义一个范数函数f(u + vi) = u + v，以将高斯整数u + vi转换成普通整数来比较大小。在每个步骤k中，余数的范数f(rk)必须小于前一个余数的范数f(rk−1)。因为范数是非负整数并且在每一步都减小，所以辗转相除法在有限步内一定能结丛。最后一个非零余数即是α和β的最大公约数，即能同时整除α和β的整数中范数最大的一个。若把乘以±1或±i的所得结果考虑在内，那么可以说α和β的最大公约数是唯一的。

很多其他应用如线性丢番图方程、中国剩余定理都适用于高斯整数，高斯整数的连分数也可以用辗转相除法定义。

欧几里得整环

如果一个支持两种二元运算（+ 和 ·）的元素的集合形成一个交换环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时的艾森斯坦整数），但在其他情况下并非总是正确的。惟一分解性质在分圆域的失效使恩斯特·库默尔发明了理想数的概念，随后理查德·戴德金创造了理想的概念。

二次整数的惟一分解

二次整数环对于解释欧几里得整环很有帮助。二次整数是高斯整数的推广，高斯整数中的虚数单位i被替换成一个复数ω。二次整数的形式是u + vω，其中u和v是整数，ω有两种形式，取决于参数D。如果D不等于四的倍数加一，那么：

如果D等于四的倍数加一，那么：

如果二次整数环有像上文用来比较高斯整数的那样的范数函数，那么它就是规范欧几里德整环。只有当D = −11, −7, −3, −2, −1, 2, 3, 5, 6, 7, 11, 13, 17, 19, 21, 29, 33, 37, 41, 57或73时，二次整数环才是规范欧几里德整环。D = −1和−3时的二次整数分别叫作高斯整数和艾森斯坦整数。

但如果范数函数f可以是任何欧几里得函数，那么使二次整数环是欧几里得整环的D的可能值到目前为止还不确定。是欧几里得整环但不是规范欧几里德整环的第一个例子（D=69）发表于1994年。温伯格于1973年证明，在广义黎曼猜想成立的前提下，D>0时的二次整数环是欧几里得整环，当且仅当它是一个主理想环。

非交换环

辗转相除法也可以应用至非交换环，如赫尔维茨四元数。令α和β表示这样一个环中的两个元素。他们有右公约数δ如果α = ξδ，β = ηδ（ξ和η是环中的元素）。同样，他们有左公约数δ如果α = δξ，β = δη（ξ和η是环中的元素）。因为乘法不符合交换律，也就有两个版本的辗转相除法，一个计算右公约数，一个计算左公约数。例如对于右公约数，辗转相除法求最大公约数的第一步可以写成：

其中ψ0是商，ρ0是余数。对于左公约数，第一步过程是：

不管是哪一种，这个过程都会重复到最大左公约数或者最大右公约数计算出，像在欧几里得整环中一样，ρ0的“大小”一定小于β，并且对于ρ0只有有限种的可能大小，这样才能保证算法能够结丛。

由辗转相除法得出的大多数结果都适用于非交换环。例如，贝祖等式表明最大右公约数可以表示成α的倍数和β的倍数的和，即，存在σ和τ使：

对于最大左公约数，等式如下：

贝祖等式可以用来解非交换环的丢番图方程。

推广至其他数学结构

辗转相除法有三个性质保证它不会永远进行下去。第一，它可以写成一系列递归式：

其中每一个余数都比前一个余数小，|rk| rk−1|。第二，余数的大小有严格下限，如|rk| ≥ 0。第三，小于|rk|的数的数量是有限的。辗转相除法推广至其他数学结构，如缠结（英语：tangle (mathematics)）和超限序数时仍保持这种性质。

辗转相除法的一个重要推广是代数几何中格罗布纳基的概念。像前文所述，a和b的最大公约数g 是它们的理想的生成元素。也就是说，对任何整数s和t，存在另一个整数m使：

虽然这对一元多项式也成立，但是对多元多项式就不成立了。在多元多项式的情况下，生成元素的有限集合g1、g2……可以定义如下：

其中s、t和mk是多元多项式。任何这样的多元多项式f可以表示成生成多项式的和加上惟一的余数多项式r, 通常叫做多项式f的一般形式。

虽然商多项式qk可能不惟一。这些生成多项式的集合就叫做格罗布纳基。

参考资料

书籍

（英文）Cohen H. A Course in Computational Algebraic Number Theory. New York: Springer-Verlag. 1993. ISBN 0-387-55640-0. 

（英文）Cohn H. Advanced Number Theory. New York: Dover. 1962. ISBN 0-486-64023-X. 

（英文）Cormen TH, Leiserson CE, Rivest RL, and Stein C. Introduction to Algorithms 2nd. MIT Press and McGraw–Hill. 2001. ISBN 0262032937. 

（英文）Cox D, Little J, and O"Shea D. Ideals, Varieties, and Algorithms: An Introduction to Computational Algebraic Geometry and Commutative Algebra 2nd. Springer-Verlag. 1997. ISBN 0-387-94680-2. 

（英文）狄利克雷.Richard Dedekind, 编. Vorlesungen über Zahlentheorie. Braunschweig: Vieweg. 1894. 

（英文）戈弗雷·哈罗德·哈代,Wright EM[revised by D.R. Heath-Brown and J.H. Silverman]. An Introduction to the Theory of Numbers 6th. Oxford: Clarendon Press. 2008. ISBN 0199219869. 

（英文）高德纳. The Art of Computer Programming（计算机程序设计艺术）, Volume 2: Seminumerical Algorithms 3rd. Addison–Wesley. 1997. ISBN 0201896842. 

（英文）LeVeque WJ. Fundamentals of Number Theory. New York: Dover. 1977. ISBN 0-486-68906-9. 

（英文）Mollin RA. Fundamental Number Theory with Applications 2nd. Boca Raton: Chapman & Hall/CRC. 2008. ISBN 9781420066593. 

（英文）Ore Ø. Number Theory and Its History. New York: McGraw–Hill. 1948. ISBN 0486656209. 

（英文）Rosen KH. Elementary Number Theory and its Applications 4th. Reading, MA: Addison–Wesley. 2000. ISBN 0201870738. 

（英文）Schroeder MR. Number Theory in Science and Communication 4th. Springer-Verlag. 2005. ISBN 0387158006. 

（英文）Stark H. An Introduction to Number Theory. MIT Press. 1978. ISBN 0-262-69060-8. 

（英文）Stillwell J. Numbers and Geometry. New York: Springer-Verlag. 1997. ISBN 0-387-98289-2. 

（英文）Tattersall JJ. Elementary number theory in nine chapters. Cambridge:Cambridge University Press. 2005. ISBN 9780521850148. 

（英文）Uspensky JV, Heaslet MA. Elementary Number Theory. New York: McGraw–Hill. 1939. ISBN 0070667500. 

免责声明：以上内容版权归原作者所有，如有侵犯您的原创版权请告知，我们将尽快删除相关内容。感谢每一位辛勤著写的作者，感谢每一位的分享。