辗转相除法

function gcd(a, b)    while b ≠ 0        t ← b        b ← a mod b        a ← t    return a

 1int 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}

1def gcd(a, b):2    while b != 0:3        t = a % b4        a = b5        b = t6    return a

function gcd(a, b)    if a = 0       return b    while b ≠ 0        if a > b           a ← a − b        else           b ← b − a    return a

function gcd(a, b)    if b = 0       return a    else       return gcd(b, a mod b)

1int gcd(int n,int m)2{3        if(m==0)4                return n;5        else6                return gcd(m,n%m);7}

 1public class MethodOfSuccessiveDivision { 2    public static void main(String args) { 3        System.out.println(gcd(1071,462)); 4    } 5    public static int gcd(int a,int b){ 6        if(b == 0){ 7            return a; 8        }else{ 9            return gcd(b,a%b);10        }11    }12}

Python3版本：

1def 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。

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

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

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

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

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

几个世纪之后，辗转相除法又分别被中国人和印度人独立发现，主要用来解天文学中用到的丢番图方程以及制定准确的历法。5世纪末，印度数学家、天文学家阿里亚哈塔曾称辗转相除法为“粉碎机”，这可能是因为它在解丢番图方程时很有效。在中国，《九章算术》中提到了一种类似辗转相减法的“更相减损术”。《孙子算经》中则出现了中国剩余定理的一个特例，但是直到1247年秦九韶才于其《数学九章》中解答了该定理的一般情况，当中用到了他发明的大衍求一术。此法的其中一部分实际上便是辗转相除的原理，秦九韶在书中对此有明确表述。在欧洲，辗转相除法首次出现于克劳德·巴希特（英语：Claude Gaspard Bachet de Méziriac）的著作《愉悦讨喜的问题》（）的第二版在欧洲，辗转相除法被用于丢番图方程和构建连分数。后来，英国数学家桑德森（英语：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）基于辗转相除法创造了一种二人游戏，叫做“欧几里得游戏”。这个游戏有最优策略。游戏开始于两列分别为和个棋子组成的序列，玩家轮流从较长一列中取走较短一列棋子数量的倍的棋子。如果两列棋子和分别由和个棋子组成，其中大于，那么玩家可以将序列的棋子数量减少为自然数 − 。最后率先将一列棋子清空的玩家胜出。

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

整数和可以从辗转相除法算出的商₀、₁……计算出。 从辗转相除法的最后一步开始，可以表示成前一步的商₋₁和前两步的余数₋₂和₋₃：

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

将这两行式子先后代入第一个式子，可以将表示成₋₄和₋₅的线性和。重复进行迭代直到出现和：

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

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

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

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

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

算法开始时：

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

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

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

因为₋₂和₋₁被假定是正确的，所以可以用和表示：

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

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

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

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

这使辗转相除法化简为：

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

由上式可以得出 = (−1)+1 ( ₂₂ − ₁₂ )。

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

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

两边都乘以：

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

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

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

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

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

令为和的最大公约数，a、b都能被g整除，故 + 能够被整除。所以，一定能够被整除，不然方程就无解。方程两边若同时除以 ${\displaystyle \frac{c}{g}}$和可以用扩展欧几里得算法求解。所以这个丢番图方程的一个解即是：

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

或者可以写成：

所以相邻两个解的之间的差是${\displaystyle \frac{b}{g}}$之间的差是${\displaystyle \frac{a}{g}}$取遍所有整数时，方程所有的解都可以从 (₁, ₁) 计算出来。如果限制为正整数解 ( > 0,  > 0) 的话，那么解的数量就可能是有限的。有时候，这种对解的限制使丢番图方程在未知数个数比方程数更多的情况下仍然能有唯一解，而在允许实数解的线性方程组中，这种情况是不可能的。

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

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

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

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

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

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

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

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

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

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

第三个式子可以代入分母中的₁/₀：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

其中γ是欧拉-马歇罗尼常数，ζ′是黎曼ζ函数的导数。公式最左边的${\displaystyle \frac{12}{{\mathrm{\pi <!--\; \pi \; -->}}^2}\ln <!--\; \; -->2}$)是冯·曼戈尔特函数。

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

将()的近似公式代入，得到()的近似：

在辗转相除法的每一步中，商和余数都通过₋₂和₋₁求出：

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

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

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

综合考虑算法需要的步数和每一步的计算开销，辗转相除法随两个数字和的平均位数成平方级的速度增长(2)。设₀、₁、…、₋₁表示计算过程中的余数₀、₁、…、₋₁的位数，因为算法的步数随线性增长，所以算法的运算时间为：

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

计算两数和的最大公约数有一个效率很慢的算法：将除以从2到之间的每一个整数以计算出它们所有的公约数，其中最大的一个即是最大公约数。在这个算法中，步骤数随线性增长，也就是随输入数字的位数呈指数级增长。另一个很低效的算法是计算出两个数的所有素因数（见上文），最大公约数等于所有公共素因数的乘积。但是整数分解算法效率极低，很多现代的加密系统甚至依靠这种低效率来防止资料被破解。

除了辗转相除法之外，也有一些高效的算法存在，如二进制最大公约数算法将除法操作替换成了二进制的移位，以进一步提高用计算机运算时的效率。但是，这种改变并没有降低算法的复杂度（仍然是(²)），虽然它在计算机上确实比辗转相除法快些。也可以通过只检视和的前几位数来进一步提高效率，不过效果并不明显。二进制版的算法还可以扩展到其它进制，效率最多可以提升五倍。

对于超过25,000位数的大数，有一种改进使算法复杂度降低至平方级以下，如Schönhage、Stehlé、Zimmermann等人提出的算法。这些算法利用2×2的矩阵（见上文）。这些亚平方级的算法复杂度通常是( (log )2 (log log ))。

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

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

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

于是我们可以写出它的有限连分数形式：。如果算法无法结束，那么/是无理数，可以写成无限的连分数形式：。无限连分数的一个例子是：黄金分割比 = 和2的算术平方根：${\displaystyle \sqrt{2}=}$和，几乎所有/都是无理数。

如果算法不结束，也可以在第步时终止计算，得到近似连分数。终止时的越大，则近似越准确。连分数/的分子和分母互素并满足下式：

其中递归的初始值是₋₁ = ₋₂ = 1，₋₂ = ₋₁ = 0。/是/在分母是的数中最精确的有理数近似值：

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

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

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

和

()除以()得到余数：

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

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

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

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

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

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

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

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

如果一个支持两种二元运算（+ 和 ·）的元素的集合形成一个交换环并且可以使用辗转相除法求最大公约数，那么这个集合叫做欧几里得整环。这两个二元运算不必是平常算数中的加法和乘法，它们可以是更广泛的概念，如群或幺半群中的运算。但是这些运算仍然需要遵守交换律、结合律、分配律。

推广之后的辗转相除法需要一个欧几里得函数，即一个将映射到非负整数集合的函数，使得对于中非零元素和，中存在和满足 = + ，() < ()。例如上文中用于高斯整数的范数函数。这个函数可以是数的绝对值或模，也可以是多项式的次数，只要辗转相除法计算过程中它的值不断减小就行，这样算法便能在有限步内结束。这非常依赖于非负整数的良序性，即每个非空的非负整数集合都有一个最小数。

任何欧几里得整环都满足算数基本定理：欧几里得整环中的数可以惟一分解。所以任何欧几里得整环都是惟一分解整环，但反之不然。欧几里得整环是GCD整环（任意两元素都存在最大公约数的整环）的子类。也就是说，在某些整环中，两元素存在最大公约数但却不能用辗转相除法计算。欧几里得整环都是主理想环，即其中每一个理想都是主理想，但并不是每个主理想环都是欧几里得整环。

欧几里得整环的惟一分解性质在很多场合都非常有用。例如，高斯整数的惟一分解性质可以方便地导出勾股数的公式，或者证明费马平方和定理。惟一分解性质也是加百利·拉梅于1847年基于约瑟夫·刘维尔的建议发表的证明费马最后定理的尝试中的关键部分。拉梅的尝试需要形如 + ω的数的惟一分解性质，其中和是整数，ω = 2π/是1的次方根，即ω = 1。虽然这对于某些成立（如=3时的艾森斯坦整数），但在其他情况下并非总是正确的。惟一分解性质在分圆域的失效使恩斯特·库默尔发明了理想数的概念，随后理查德·戴德金创造了理想的概念。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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