輾轉相除法

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

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

一个24×60的长方形正好被十个12×12的方格填满，其中12是24和60的最大公约数。一般地，当且仅当c是a和b的公约数时，a×b尺寸的长方形可被边长c的正方形正好填满。

令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整除。[5]

我们可以用右图来解释最大公约数的概念：[6]設一个长方形的边长为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的最大公约数是两数共有的素因数的乘积。[7]例如，462可以分解成2 × 3 × 7 × 11；1071可以分解成3 × 3 × 7 × 17。462和1071的最大公约数等于它们共有的素因数的乘积3 × 7 = 21。如果两数没有公共的素因数，那么它们的最大公约数是1，也即这两个数互素。辗转相除法的优点就在於它能以有系統的方式求出兩數的最大公约数，而無需分別對它們作因式分解。[8][9]大数的素因数分解被認為是一個困難的問題，即使是现代的计算机也非常难於處理，所以许多加密系统的原理都是建基於此。[10]

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

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

GCD(a, b, c) = GCD(a, GCD(b, c)) = GCD(GCD(a, b), c) = GCD(GCD(a, c), b).

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

下文的論證會用到三種相關的数学方法，分別是数学归纳法、递归和无穷递降。数学归纳法[14]经常用来证明某個定理對所有自然数成立：[15]首先证明定理对一个特定的数n₀成立（通常是1）；然后證明如果定理对自然数n成立的話，那麼它对自然数n + 1成立。這樣，便可證明定理对所有大于n₀的自然数也成立。递归[16]是将相关的数组成一个数列(a₁, a₂, a₃...)，[17]當中除初始項外，其中每一项都用前一项或前几项表示。如斐波那契数列就是递归的，每一项F_n都等于F_n−1 + F_n−2（n≧2）。辗转相除法中的一些等式也是递归的。最后，无穷递降[18]是用方程的一个自然数解导出比它小的自然数解。[19]但是，这种转化不能永远进行下去，因为只有有限個小於原來的自然数解的自然数。所以，要麼方程無解，不然在有限步内必然能得出最小的自然數解。在下文會用到此法來证明辗转相除法一定会在有限步内结束。

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

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

r_k−2 = q_k r_k−1 + r_k

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

為求簡明，以下只說明如何求兩個非負整數a和b的最大公約數（負數的情況是簡單的）。在第一步计算时（k = 0），设r₋₂和r₋₁分别等于a和b，第2步（此时k = 1）时计算r₋₁（即b）和r₀（第一步计算产生的余数）相除产生的商和余数，以此类推。整个算法可以用如下等式表示：

a = q₀ b + r₀

b = q₁ r₀ + r₁

r₀ = q₂ r₁ + r₂

r₁ = q₃ r₂ + r₃

…

如果有a < b，算法的第一步實際上會把兩個數字交換，因為這時a除以b所得的商q₀會等于0，余数r₀則等于a。然後，算法的第二步便是把b除以a，再計算所得之商和餘數。所以，對於k ≥ 0總有r_k<r_k−1，即运算的每一步中得出的余数一定小于上一步计算的余数。

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

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

1. 证明r_N−1同时整除a和b：

   因为余数r_N是0，r_N−1能够整除r_N−2：

   r_N−2 = q_N r_N−1

   因为r_N−1能够整除r_N−2，所以也能够整除r_N−3：

   r_N−3 = q_N−1 r_N−2 + r_N−1

   同理可证r_N−1可以整除所有之前步骤的余数，包括a和b，即r_N−1是a和b的公约数，r_N−1 ≤ g。

2. 证明最大公约数g能整除r_N-1：

   根据定义，a和b可以写成g的倍数：a = mg、b = ng，其中m和n是自然数。因为r₀ = a − q₀b = mg − q₀ng = (m − q₀n)g，所以g整除r₀。同理可证g整除每个余数r₁, r₂, ..., r_N-1。因為最大公约数g整除r_N−1，因而g ≤ r_N−1。

因为第一步的证明告诉我们r_N−1 ≤ g，所以g = r_N−1。即：[22][23]

g = GCD(a, b) = GCD(b, r₀) = GCD(r₀, r₁) = … = GCD(r_N−2, r_N−1) = r_N−1

算法的演示动画。最初的绿色矩形的长和宽分别是a = 1071、b = 462，从中不断铺上462×462的正方形直到剩下部分面积是462×147；然后再铺上147×147的正方形直至剩下21×147的面积；最后，铺上21×21的正方形时，绿色部分就没有了。即21是1071和462的最大公约数。

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

1071 = 2 × 462 + 147.

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

462 = 3 × 147 + 21.

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

147 = 7 × 21 + 0.

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

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

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

r_k−2 = q_k r_k−1 + r_k

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

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

r_k ≡ r_k−2 mod r_k−1

辗转相除法可用伪代码表示，比如除法版本可以寫成[26]

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

c++版本：

int gcd(int m,int n)
{
        int t = 1;
        while(t != 0)
        {
                t=m%n;
                m=n;
                n=t;
        }
        return m;
}

Python3版本：

def gcd(a, b):
    while b != 0:
        t = a % b
        a = b
        b = t
    return a

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

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

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_k−1和r_k−2。假定第k次循环开始时a大于b，那么a等于r_k−2，因为r_k−2 > r_k−1。在循环过程中，a重复减去b直到比b小，此时a就是下一个余数r_k；然后b重复减去a直到比a小，此时b就是下一个余数r_k+1；重复执行直到b = 0。

以下是递归版本[28]：

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

c++递归版本如下：

int gcd(int n,int m)
{
        if(m==0)
                return n;
        else
                return gcd(m,n%m);
}

Java版本：

public class MethodOfSuccessiveDivision {
    public static void main(String[] args) {
        System.out.println(gcd(1071,462));
    }
    public static int gcd(int a,int b){
        if(b == 0){
            return a;
        }else{
            return gcd(b,a%b);
        }
    }
}

Python3版本：

def gcd(a, b):
    if b == 0:
        return a
    else:
        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。

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

r_k−2 = q_k r_k−1 + r_k

即假設r_k−1 > r_k > 0。然後使用以下式子计算出一个负的余数e_k：

r_k−2 = (q_k + 1) r_k−1 + e_k

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

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

整数s和t可以从辗转相除法算出的商q₀、q₁……计算出。[62] 从辗转相除法的最后一步开始，g可以表示成前一步的商q_N−1和前两步的余数r_N−2和r_N−3：

g = r_N−1 = r_N−3 − q_N−1 r_N−2

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

r_N−2 = r_N−4 − q_N−2 r_N−3

r_N−3 = r_N−5 − q_N−3 r_N−4

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

r₂ = r₀ − q₂ r₁

r₁ = b − q₁ r₀

r₀ = a − q₀ b

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

贝祖等式提供了另一种定义a和b的最大公约数g的方法。[11]考虑形如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，便有：

mg = msa + mtb

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

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

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

s_k = s_k−2 − q_ks_k−1

t_k = t_k−2 − q_kt_k−1

算法开始时：

s₋₂ = 1, t₋₂ = 0

s₋₁ = 0, t₋₁ = 1

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

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

r_j = s_j a + t_j b

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

r_k = r_k−2 − q_kr_k−1

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

r_k = (s_k−2 a + t_k−2 b) − q_k(s_k−1 a + t_k−1 b)

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

r_k = s_k a + t_k b = (s_k−2 − q_ks_k−1) a + (t_k−2 − q_kt_k−1) b

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

a = q₀ b + r₀

b = q₁ r₀ + r₁

…

r_N−2 = q_N r_N−1 + 0

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

${\displaystyle {\begin{pmatrix}a\\b\end{pmatrix}}={\begin{pmatrix}q_{0}&1\\1&0\end{pmatrix}}{\begin{pmatrix}b\\r_{0}\end{pmatrix}}={\begin{pmatrix}q_{0}&1\\1&0\end{pmatrix}}{\begin{pmatrix}q_{1}&1\\1&0\end{pmatrix}}{\begin{pmatrix}r_{0}\\r_{1}\end{pmatrix}}=\cdots =\prod _{i=0}^{N}{\begin{pmatrix}q_{i}&1\\1&0\end{pmatrix}}{\begin{pmatrix}r_{N-1}\\0\end{pmatrix}}}$

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

${\displaystyle \mathbf {M} ={\begin{pmatrix}m_{11}&m_{12}\\m_{21}&m_{22}\end{pmatrix}}=\prod _{i=0}^{N}{\begin{pmatrix}q_{i}&1\\1&0\end{pmatrix}}={\begin{pmatrix}q_{0}&1\\1&0\end{pmatrix}}{\begin{pmatrix}q_{1}&1\\1&0\end{pmatrix}}\cdots {\begin{pmatrix}q_{N}&1\\1&0\end{pmatrix}}}$

这使辗转相除法化简为：

${\displaystyle {\begin{pmatrix}a\\b\end{pmatrix}}=\mathbf {M} {\begin{pmatrix}r_{N-1}\\0\end{pmatrix}}=\mathbf {M} {\begin{pmatrix}g\\0\end{pmatrix}}}$

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

${\displaystyle {\begin{pmatrix}g\\0\end{pmatrix}}=\mathbf {M} ^{-1}{\begin{pmatrix}a\\b\end{pmatrix}}=(-1)^{N+1}{\begin{pmatrix}m_{22}&-m_{12}\\-m_{21}&m_{11}\end{pmatrix}}{\begin{pmatrix}a\\b\end{pmatrix}}}$

由上式可以得出g = (−1)^N+1 ( m₂₂ a − m₁₂ b)。

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

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

1 = su + tw。

两边都乘以v：

v = suv + twv = sL + twv

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

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

L = p₁p₂…p_m = q₁q₂…q_n

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

线性丢番图方程：9x + 12y = 483的图像，它的解用蓝点表示。

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

${\displaystyle ax+by=c}$

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

${\displaystyle ax\equiv c{\pmod {b}}}$

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

${\displaystyle sa+tb=g}$

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

${\displaystyle {\begin{aligned}x_{1}=s({\tfrac {c}{g}})\\y_{1}=t({\tfrac {c}{g}})\end{aligned}}}$

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

${\displaystyle ax_{1}+by_{1}=c=ax_{2}+by_{2}}$

或者可以写成：

${\displaystyle a(x_{1}-x_{2})=b(y_{2}-y_{1})}$

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

${\displaystyle {\begin{aligned}x=x_{1}-{\tfrac {bt}{g}}\\y=y_{1}+{\tfrac {at}{g}}\end{aligned}}}$

当t取遍所有整数时，方程所有的解都可以从 (x₁, y₁) 计算出来。如果限制為正整数解 (x > 0, y > 0) 的话，那么解的数量就可能是有限的。有時候，这种对解的限制使丢番图方程在未知数個數比方程數更多的情况下仍然能有唯一解[74]，而在允許實數解的线性方程组中，这種情況是不可能的。

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

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

ax + my = 1

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

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

${\displaystyle {\begin{aligned}x_{1}&\equiv x{\pmod {m_{1}}}\\x_{2}&\equiv x{\pmod {m_{2}}}\\\vdots &\\x_{N}&\equiv x{\pmod {m_{N}}}\end{aligned}}}$

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

${\displaystyle M_{i}=M/m_{i}}$

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

${\displaystyle M_{i}h_{i}\equiv 1{\pmod {m_{i}}}}$

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

${\displaystyle x\equiv (x_{1}M_{1}h_{1}+x_{2}M_{2}h_{2}+\cdots +x_{N}M_{N}h_{N})\mod M}$

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

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

${\displaystyle {\begin{aligned}{\frac {a}{b}}&=q_{0}+{\frac {r_{0}}{b}}\\{\frac {b}{r_{0}}}&=q_{1}+{\frac {r_{1}}{r_{0}}}\\{\frac {r_{0}}{r_{1}}}&=q_{2}+{\frac {r_{2}}{r_{1}}}\\\vdots &\\{\frac {r_{k-2}}{r_{k-1}}}&=q_{k}+{\frac {r_{k}}{r_{k-1}}}\\\vdots &\\{\frac {r_{N-2}}{r_{N-1}}}&=q_{N}\\\end{aligned}}}$

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

${\displaystyle {\frac {a}{b}}=q_{0}+{\frac {1}{q_{1}+{\frac {r_{1}}{r_{0}}}}}}$

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

${\displaystyle {\frac {a}{b}}=q_{0}+{\frac {1}{q_{1}+{\frac {1}{q_{2}+{\frac {r_{2}}{r_{1}}}}}}}}$

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

${\displaystyle {\frac {a}{b}}=q_{0}+{\dfrac {1}{q_{1}+{\dfrac {1}{q_{2}+{\dfrac {1}{\ddots +{\dfrac {1}{q_{N}}}}}}}}}=[q_{0};q_{1},q_{2},\cdots ,q_{N}]}$

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

${\displaystyle {\frac {1071}{462}}=2+{\frac {1}{3+{\frac {1}{7}}}}=[2;3,7]}$

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

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

T(a, b) = T(m, n)

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

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

T(a, b) = 1 + T(b, r₀) = 2 + T(r₀, r₁) = … = N + T(r_N−2, r_N−1) = N + 1

其中，根據定义有T(x, 0) = 0。[92]

假设用辗转相除法求自然数a和b（a > b > 0）的最大公约数需要N步，那么满足这一条件的a和b的最小值分别是斐波那契数F_N+2和F_N+1。[94]这可以用数学归纳法证明。[95]假设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₀的最小值是 F_M+1 和 F_M。所以a的最小值是当 q₀ = 1 的时候，此时 a = b + r₀ = F_M+1 + F_M = F_M+2。1844年，加百利·拉梅发现这个证明标志着计算复杂性理论的诞生。[96]这也是斐波那契数列的第一个实际应用。[94]

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

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

${\displaystyle T(a)={\frac {1}{a}}\sum _{0\leq b<a}T(a,b)}$

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

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

${\displaystyle \tau (a)={\frac {1}{\varphi (a)}}\sum _{0\leq b<a,\mathrm {GCD} (a,b)=1}T(a,b)}$

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

${\displaystyle \tau (a)={\frac {12}{\pi ^{2}}}\ln 2\ln a+C+O(a^{-{\frac {1}{6}}+\varepsilon })}$

誤差項的增長率為O(a^{−(1/6) + ε})，其中ε是无穷小量。公式中的常数C等于：

${\displaystyle C={\frac {1}{2}}+6({\frac {\ln 2}{\pi ^{2}}})(4\gamma -24\pi ^{2}\zeta '(2)+3\ln 2-2)\approx 1.467}$

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

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

${\displaystyle T(a)={\frac {1}{a}}\sum _{d|a}\varphi (d)\tau (d)}$

所以也可以由以下公式近似：[106]

${\displaystyle T(a)\approx C+{\frac {12}{\pi ^{2}}}\ln 2(\ln a-\sum _{d|a}{\frac {\Lambda (d)}{d}})}$

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

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

${\displaystyle Y(n)={\frac {1}{n^{2}}}\sum _{a=1}^{n}\sum _{b=1}^{n}T(a,b)={\frac {1}{n}}\sum _{a=1}^{n}T(a)}$

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

${\displaystyle Y(n)\approx {\frac {12}{\pi ^{2}}}\ln 2\ln n+0.06}$

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

r_k−2 = q_k r_k−1 + r_k

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

r_k = r_k−2 − q_k r_k−1

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

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

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

${\displaystyle O{\Big (}\sum _{i<N}h_{i}(h_{i}-h_{i+1}+2){\Big )}\subseteq O{\Big (}h\sum _{i<N}(h_{i}-h_{i+1}+2){\Big )}\subseteq O(h(h_{0}+2N))\subseteq O(h^{2})}$

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

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

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

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

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

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

a/b =mg/ng = m/n

于是我们可以写出它的有限连分数形式：[q₀; q₁, q₂, …, q_N]。如果算法无法结束，那么a/b是无理数，可以写成无限的连分数形式： [q₀; q₁, q₂, …] 。无限连分数的一个例子是：黄金分割比 φ = [1; 1, 1, …] 和2的算術平方根：${\displaystyle {\sqrt {2}}=[1;2,2,\ldots ]}$。通常，算法能够结束的可能性是很低的，因为对于实数a和b，几乎所有a/b都是无理数。

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

m_k = q_k m_k−1 + m_k−2

n_k = q_k n_k−1 + n_k−2

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

${\displaystyle \left|{\frac {a}{b}}-{\frac {m_{k}}{n_{k}}}\right|<{\frac {1}{n_{k}^{2}}}}$

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

r_k−2(x) = q_k(x) r_k−1(x) + r_k(x)

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

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

a(x) = x⁴ − 4x³ + 4 x² − 3x + 14 = (x² − 5x + 7)(x² + x + 2)

和

b(x) = x⁴ + 8x³ + 12x² + 17x + 6 = (x² + 7x + 3)(x² + x + 2).

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

${\displaystyle r_{0}(x)=x^{3}+{\frac {2}{3}}x^{2}+{\frac {5}{3}}x-{\frac {2}{3}}}$

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

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

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

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

高斯素数u + vi在复平面的分布，其中u² + v²小于500。

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

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

r_k = r_k−2 − q_k r_k−1

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

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

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

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

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

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

艾森斯坦素数u + vω在复平面的分布（范数小于500，ω等于1的立方根）。

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

${\displaystyle \omega ={\sqrt {D}}}$

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

${\displaystyle \omega ={\frac {1+{\sqrt {D}}}{2}}}$

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

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

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

ρ₀ = α − ψ₀β = (ξ − ψ₀η)δ

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

ρ₀ = α − βψ₀ = δ(ξ − ηψ₀)

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

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

Γ_右 = σα + τβ

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

Γ_左 = ασ + βτ

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