輾轉相除法

輾轉相除法的演示動畫：
兩條線段長分別可表示252和105，則其中每一小分段長代表最大公因數21。如動畫所示，只要輾轉地從大數中減去小數，直到其中一段的長度為0，此時剩下的一條線段的長度就是252和105的最大公因數。

在數學中，輾轉相除法，又稱歐幾里得算法（英語：Euclidean algorithm），是求最大公約數的算法。輾轉相除法首次出現於歐幾里得的《幾何原本》（第VII卷，命題i和ii）中，而在中國則可以追溯至東漢出現的《九章算術》。

兩個整數的最大公約數是能夠同時整除它們的最大的正整數。輾轉相除法基於如下原理：兩個整數的最大公約數等於其中較小的數和兩數相除餘數的最大公約數。例如，欲求252和105的最大公約數（$252=21\times 12;105=21\times 5$）；因為$252\div 105=2...42$，所以這個最大公約數也是42與105的最大公約數($42=21\times 2$)。在這個過程中，較大的數縮小了，所以繼續進行同樣的計算可以不斷縮小這兩個數直至餘數為零。這時，所剩下的還沒有變成零的數就是兩數的最大公約數。由輾轉相除法也可以推出，兩數的最大公約數可以用兩數的整數倍相加來表示，如$21=5\times 105+(-2)\times 252$。這個重要的結論叫做貝祖定理。

輾轉相除法最早出現在歐幾里得的《幾何原本》中（大約公元前300年），所以它是現行的算法中歷史最悠久的。這個算法原先只用來處理自然數和幾何長度（相當於正實數），但在19世紀，輾轉相除法被推廣至其他類型的數學物件，如高斯整數和一元多項式。由此，引申出歐幾里得整環等等的一些現代抽象代數概念。後來，輾轉相除法又擴展至其他數學領域，如紐結理論和多元多項式。

輾轉相除法有很多應用，它甚至可以用來生成全世界不同文化中的傳統音樂節奏。在現代密碼學方面，它是RSA算法（一種在電子商務中廣泛使用的公鑰加密算法）的重要部分。它還被用來解丟番圖方程，比如尋找滿足中國剩餘定理的數，或者求有限域中元素的逆。輾轉相除法還可以用來構造連分數，在施圖姆定理和一些整數分解算法中也有應用。輾轉相除法是現代數論中的基本工具。

輾轉相除法處理大數時非常高效，如果用除法而不是減法實現，它需要的步驟不會超過較小數的位數（十進制下）的五倍。拉梅於1844年證明了這點，同時這也標誌著計算複雜性理論的開端。

背景

最大公約數

歐幾里得的輾轉相除法計算的是兩個自然數$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。

一個24×60的長方形正好被十個12×12的方格填滿，其中12是24和60的最大公約數。一般地，當且僅當$c$是$a$和$b$的公約數時，$a\times 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$整除。

我們可以用右圖來解釋最大公約數的概念：設一個長方形的邊長為$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$生成的主理想。最大公約數的這個定義和其他定義的等價性將在下面描述。

三個數的最大公約數的定義和兩個數的相同，即是它們共有的素因數的積，它們或者也可以按下式計算：

$\gcd(a,b,c)=\gcd(a,\gcd(b,c))=\gcd(\gcd(a,b),c)=\gcd(\gcd(a,c),b).$

所以，歐幾里得的輾轉相除法實際可以計算任意多整數的最大公約數。

歸納、遞歸和無窮遞降

下文的論證會用到三種相關的數學方法，分別是數學歸納法、遞歸和無窮遞降。數學歸納法經常用來證明某個定理對所有自然數成立：首先證明定理對一個特定的數$n_{0}$成立（通常是1）；然後證明如果定理對自然數$n$成立的話，那麼它對自然數$n+1$成立。這樣，便可證明定理對所有大於$n_{0}$的自然數也成立。遞歸是將相關的數組成一個數列（$a_{1},a_{2},a_{3},\cdots$），當中除初始項外，其中每一項都用前一項或前幾項表示。如斐波那契數列就是遞歸的，每一項$F_{n}$都等於$F_{n-1}+F_{n-2}$（$n\geqq 2$）。輾轉相除法中的一些等式也是遞歸的。最後，無窮遞降是用方程的一個自然數解導出比它小的自然數解。但是，這種轉化不能永遠進行下去，因為只有有限個小於原來的自然數解的自然數。所以，要麼方程無解，不然在有限步內必然能得出最小的自然數解。在下文會用到此法來證明輾轉相除法一定會在有限步內結束。

算法描述

計算過程

輾轉相除法是一種遞歸算法，每一步計算的輸出值就是下一步計算時的輸入值。設$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\leq r_{k}<r_{k-1}$。也就是$r_{k-2}$要不斷減去$r_{k-1}$直到比$r_{k-1}$小。

為求簡明，以下只說明如何求兩個非負整數$a$和$b$的最大公約數（負數的情況是簡單的）。在第一步計算時（$k=0$），設$r_{-2}$和$r_{-1}$分別等於$a$和$b$，第2步（此時$k=1$）時計算$r_{-1}$（即$b$）和$r_{0}$（第一步計算產生的餘數）相除產生的商和餘數，以此類推。整個算法可以用如下等式表示：

如果有$a<b$，算法的第一步實際上會把兩個數字交換，因為這時$a$除以$b$所得的商$q_{0}$會等於0，餘數$r_{0}$則等於$a$。然後，算法的第二步便是把$b$除以$a$，再計算所得之商和餘數。所以，對於$k\geq 0$總有$r_{k}<r_{k-1}$，即運算的每一步中得出的餘數一定小於上一步計算的餘數。

由於每一步的餘數都在減小並且不為負數，必然存在第$n$步時$r_{n}$等於0，使算法終止，$r_{n-1}$就是$a$和$b$的最大公約數。其中$n$不可能無窮大，因為在$r_{0}$和0之間只有有限個自然數。

正確性的證明

輾轉相除法的正確性可以分成兩步來證明。在第一步，我們會證明算法的最終結果$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}$

   因爲$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}\leq g$。

2. 證明最大公約數$g$能整除$r_{n-1}$：

   根據定義，$a$和$b$可以寫成$g$的倍數：$a=mg$、$b=ng$，其中$m$和$n$是自然數。

   因爲$r_{0}=a-q_{0}b=mg-q_{0}ng=(m-q_{0}n)g$，所以$g$整除$r_{0}$。 同理可證$g$整除每個餘數$r_{1},r_{2},\ldots ,r_{n-1}$。

   因爲最大公約數$g$整除$r_{n-1}$，因而$g\leq r_{n-1}$。

3. 所以$g=r_{n-1}$。即：

   $g=\gcd(a,b)=\gcd(b,r_{0})=\gcd(r_{0},r_{1})=\ldots =\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_{0}=2$），餘數是147：

$1071=2\times 462+147.$

然後從462中不斷減去147直到小於147（可以減3次，即$q_{1}=3$），餘數是21：

$462=3\times 147+21.$

再從147中不斷減去21直到小於21（可以減7次，即$q_{2}=7$），沒有餘數：

$147=7\times 21+0.$

此時，餘數是0，所以1071和462的最大公約數是21，這和用素因數分解得出的結果相同（見上文）用表格表示如下：

步驟數	算式	商和餘數
0	$1071=462q_{0}+r_{0}$	$q_{0}=2$、$r_{0}=147$
1	$462=147q_{1}+r_{1}$	$q_{1}=3$、$r_{1}=21$
2	$147=21q_{2}+r_{2}$	$q_{2}=7$、$r_{2}=0$（算法終止）

圖形演示

輾轉相除法的計算過程可以用圖形演示。假設我們要在$a\times b$的矩形地面上鋪正方形瓷磚，並且正好鋪滿，其中$a$大於$b$。我們先嘗試用$b\times b$的瓷磚，但是留下了$r_{0}\times b$的部分，其中$r_{0}<b$。我們接着嘗試用$r_{0}\times r_{0}$的正方形瓷磚鋪，又留下了$r_{1}\times r_{0}$的部分，然後再使用$r_{1}\times r_{1}$的正方形鋪……直到全部鋪滿為止，即到某步時正方形剛好覆蓋剩餘的面積為止。此時用到的最小的正方形的邊長就是原來矩形的兩條邊長的最大公約數。在圖中，最小的正方形面積是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\leq r_{k}<r_{k-1}$。除法的算法保證這樣的商和餘數總是存在。自然數的除法算法還指出這樣的商和餘數是惟一的，但這對輾轉相除法而言並非必要。

在歐幾里得最初的描述中，商和餘數是通過連續的減法來計算的，即從$r_{k-2}$中不斷減去$r_{k-1}$直到小於$r_{k-1}$。一個更高效的做法是使用整數除法和模除來計算商和餘數：

$r_{k}\equiv r_{k-2}{\bmod {r}}_{k-1}$

計算機實現

輾轉相除法可用偽代碼表示，比如除法版本可以寫成

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;
}

Rust版本：

fn gcd(x: isize, y: isize) -> Option<isize> {
    match (x,y) {
        (0, 0)         => None,
        (a, 0)         => Some(a.abs()),
        (mut a, mut b) => { 
            while b != 0 {
                let t = b;
                b = a % b;
                a = t;
            }

            Some(a.abs()) 
        },
    }
}

Python 3版本：

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{\bmod {b}}$的作用等同於遞歸式$r_{k}\equiv r_{k-2}{\bmod {r}}_{k-1}$。變量$t$的功能是在下一個餘數$r_{k}$計算過程中臨時性地保存$r_{k-1}$的值。在一次循環結束時，變量$b$的值是前一次運算的餘數$r_{k}$，變量$a$的值是再前一次運算的餘數$r_{k-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_{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$。

以下是遞歸版本：

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

C++遞歸版本如下：

int gcd(int n,int m)
{
    return  m == 0 ? n : gcd(m, n % m);
}

Rust遞歸版本：

fn gcd(x: isize, y: isize) -> Option<isize> {
    match (x,y) {
        (0, 0)  => None,
        (a, 0)  => Some(a.abs()),
        _       => gcd(y, x % y),
    }
}

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 );
        }
    }
}

Python 3版本：

def gcd(a, b):
    return a if b == 0 else gcd(b, a % b)

例如$\gcd(1071,462)$的計算過程是：函數的第一次調用計算$\gcd(462,1071{\bmod {4}}62)=\gcd(462,147)$；下一次調用計算$\gcd(147,462{\bmod {1}}47)=\gcd(147,21)$，在接下來是$\gcd(21,147{\bmod {2}}1)=\gcd(21,0)=21$。

使用絕對值最小的餘數

在另一個版本的算法中，每一步還要把取余運算時計算出的商增加一後再重新計算餘數（此時計算出的餘數應該是負的），然後取兩個餘數的絕對值較小的數作為下一步運算時使用的餘數。取余運算後，設$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}$進行下一次運算。如利奧波德·克羅內克所指出的，這個版本需要的運算步驟是歐幾里得算法的所有版本中最少的。

歷史發展

輾轉相除法可能在歐幾里得之前幾個世紀就已經有了。圖為使用兩腳規進行測量。

輾轉相除法是目前仍然在使用的歷史最悠久的算法之一。它首次出現於《幾何原本》（卷7命題1–2、卷10命題2–3）（大約公元前300年）。在卷7中用於整數，在卷10中用於線段的長度（以現代的觀點看，線段的長度可視為正實數，也就是說輾轉相除法實際可用於實數上，但是當時未有實數的概念）。卷10中出現的算法是幾何的，兩段線段a和b的最大公約數是a和b的公度中的最大值。

這個算法可能並非歐幾里得發明，因為他也有將先前其他數學家的一些成果編進他的《幾何原本》。數學家、歷史學家范德瓦爾登認為卷7的內容可能來自畢達哥拉斯學院出身的數學家寫的關於數論的教科書。輾轉相除法在當時很可能已為尤得塞斯（大約公元前375年）所知 ，甚至可能更早之前就已經存在，因為歐幾里得和亞里士多德的著作中都出現了ἀνθυφαίρεσις一詞（意為「輾轉相減」）。

幾個世紀之後，輾轉相除法又分別被中國人和印度人獨立發現，主要用來解天文學中用到的丟番圖方程以及制定準確的曆法。5世紀末，印度數學家、天文學家阿里亞哈塔曾稱輾轉相除法為「粉碎機」，這可能是因為它在解丟番圖方程時很有效。在中國，《九章算術》中提到了一種類似輾轉相減法的「更相減損術」。《孫子算經》中則出現了中國剩餘定理的一個特例，但是直到1247年秦九韶才於其《數學九章》中解答了該定理的一般情況，當中用到了他發明的大衍求一術。此法的其中一部分實際上便是輾轉相除的原理，秦九韶在書中對此有明確表述。在歐洲，輾轉相除法首次出現於克勞德·巴希特的著作《愉悅討喜的問題》（Problèmes plaisants et délectables）的第二版在歐洲，輾轉相除法被用於丟番圖方程和構建連分數。後來，英國數學家桑德森在其著作中收編了擴展歐幾里得算法，作為一個有效計算連分數的方法。他將此法的來源歸名於羅傑·科茨。

19世紀，輾轉相除法促成了新數系的建立，如高斯整數和艾森斯坦整數。1815年，高斯用輾轉相除法證明高斯整數的分解是惟一的，儘管他的研究到了1832年才首度發表。高斯在他的《算數研究》（出版於1801年）中實際上也有援引這個算法，但僅是以連分數方法的形式敘述。約翰·狄利克雷是第一個將輾轉相除法作為數論的基礎的數學家。狄利克雷提出，數論中的很多結論，如分解的惟一性，在任何使輾轉相除法適用的數系中均有效。狄利克雷的數論講義後來經理查德·戴德金編輯和推廣，戴德金也有以輾轉相除法來研究代數整數。比如，他是第一個用高斯整數的分解惟一性證明費馬平方和定理的數學家。戴德金還率先定義了歐幾里得整環的概念。19世紀末，戴德金所定義的理想概念使得數論的重心不必建基於輾轉相除法，從而促進了理論的發展。

「歐幾里得算法是所有算法的鼻祖，因為它是現存最古老的非凡算法。」

——高德納，《計算機程序設計藝術，第二卷：半數值算法》，第二版 (1981), p. 318.

輾轉相除法的其他應用發展於19世紀。1829年，施圖姆將輾轉相除法用於施圖姆序列（用於確定多項式的不同實根的個數的方法）。

輾轉相除法是歷史上第一個整數關係算法，即尋找兩個可通約實數的整數關係的算法。近年來，出現了一些新穎的整數關係算法，如埃拉曼·弗格森和福爾卡德於1979年發表的弗格森-福爾卡德算法（Ferguson–Forcade algorithm） 、以及與它相關的LLL算法、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$可以從輾轉相除法算出的商$q_{0},q_{1},\cdots$計算出。 從輾轉相除法的最後一步開始，$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_{2}=r_{0}-q_{2}r_{1}$

$r_{1}=b-q_{1}r_{0}$

$r_{0}=a-q_{0}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$，便有：

$mg=msa+mtb$

所以，形如$ua+vb$的數的集合等於$g$的整數倍的集合。也就是說，任意兩個數的線性和的集合等同於它們最大公約數的整數倍的集合。$a$和$b$的最大公約數叫做$a$和$b$的理想的生成元素。這個最大公約數的定義導出了兩個現代抽象代數的概念：主理想（由單個元素生成的理想）以及主理想整環（其每一理想都是主理想的整環）。

這個結果可以解決某些實際問題。例如，考慮兩個容積分別為$a$和$b$的量杯，其中$a$和$b$為正整數。通過加入或倒去$u$倍第一個量杯的體積以及$v$倍第二個量杯的體積的液體，任何體積為$ua+vb$的液體都可以被量出（只要$ua+vb$為正數）。根據貝祖等式，凡是可以被量出的液體，其體積一定是$a$和$b$的最大公約數$g$的倍數。

擴展歐幾里得算法

主條目：擴展歐幾里得算法

貝祖等式的整數s和t可以通過擴展歐幾里得算法算出。這個擴展算法在原有輾轉相除法的基礎上增加了兩個遞歸等式：

$s_{k}=s_{k-2}-q_{k}s_{k-1}$

$t_{k}=t_{k-2}-q_{k}t_{k-1}$

算法開始時：

$s_{-2}=1$, $t_{-2}=0$

$s_{-1}=0$, $t_{-1}=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_{k}r_{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_{k}s_{k-1})a+(t_{k-2}-q_{k}t_{k-1})b$

矩陣法

整數$s$和$t$也可以用矩陣運算得出。輾轉相除法的計算過程：

$a=q_{0}b+r_{0}$

$b=q_{1}r_{0}+r_{1}$

...

$r_{N-2}=q_{N}r_{N-1}+0$

可以寫作2×2的商矩陣乘以一個2維餘數向量：

${\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}}$

令$\mathbf {M}$表示所有商矩陣的乘積：

$\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}}$

這使輾轉相除法化簡為：

${\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$，可將等式兩邊同時乘以矩陣$\mathbf {M}$的逆矩陣。$\mathbf {M}$的行列式等於$(-1)^{N+1}$，因為它等於商矩陣的行列式的乘積，而每一個的行列式都是−1。因為$\mathbf {M}$的行列式不為零，最終的餘數向量可以利用$\mathbf {M}$的逆矩陣解出：

${\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_{22}a-m_{12}b)$。

貝祖等式中的兩個整數分別是$s=(-1)^{N+1}m_{22}$、$t=(-1)^{N}m_{12}$。矩陣法的效率可前文描述的輾轉相除法的遞歸算法是相同的，每一步都有兩次乘法和兩次加法。

歐幾里得引理和唯一分解

貝祖等式對輾轉相除法的很多應用都很重要，如證明自然數的唯一分解性質假設數字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$。這個結果叫做歐幾里得引理。如果一個素數整除$L$那麼它至少整除$L$的一個因數。如果一個數$w$互素於數列$a_{1},a_{2},\ldots ,a_{n}$ 中的每一個數，則w也一定互素於它們的乘積$a_{1}\times a_{2}\times \ldots \times a_{n}$。

歐幾里得引理足以證明每一個自然數的素數分解是惟一的。我們用反證法來證明，假設$L$可以分別分解成$m$個素數和$n$個素數，即：

$L=p_{1}p_{2}\cdots p_{m}=q_{1}q_{2}\cdots q_{n}$

根據假設，每個素數$p$都能整除$L$，因此它必須能夠整除某個$q$；因為$q$也是一個素數，所以$p=q$。同理，對於每一個$p$都存在一個$q$與它相等。所以兩種分解除了順序不同以外是完全相同的。整數分解的惟一性在數學證明中有很多應用，下文將會提到。

線性丟番圖方程

線性丟番圖方程：$9x+12y=483$的圖像，它的解用藍點表示。

丟番圖方程是以亞歷山大數學家丟番圖的名字命名的一類方程，它的解被限制在整數範圍。關於整數$x$和$y$的線性丟番圖方程形如：

$ax+by=c$

其中$a$、$b$、$c$是已知整數。這個方程可以寫成關於$x$的同餘式：

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

令$g$為$a$和$b$的最大公約數，$a$、$b$都能被$g$整除，故$ax+by$能夠被$g$整除。所以，$c$一定能夠被$g$整除，不然方程就無解。方程兩邊若同時除以 ${\frac {c}{g}}$，方程就變成了貝祖等式：

$sa+tb=g$

其中$s$和$t$可以用擴展歐幾里得算法求解。所以這個丟番圖方程的一個解即是：

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

總體而言，丟番圖方程如果有解，就一定有無數個解。只需要考慮兩個解$(x_{1},y_{1})$ 和$(x_{2},y_{2})$：

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

或者可以寫成：

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

所以相鄰兩個解的$x$之間的差是${\frac {b}{g}}$，$y$之間的差是${\frac {a}{g}}$。這樣，所有的解都可以表示成：

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

當$t$取遍所有整數時，方程所有的解都可以從$(x_{1},y_{1})$計算出來。如果限制為正整數解 ($x>0$, $y>0$) 的話，那麼解的數量就可能是有限的。有時候，這種對解的限制使丟番圖方程在未知數個數比方程數更多的情況下仍然能有唯一解，而在允許實數解的線性方程組中，這種情況是不可能的。

乘法逆和RSA算法

有限域是一個支持四種運算的數集。這四種運算也通稱為加法、減法、乘法、除法，跟一般的四則運算有相同的性質，如交換律、結合律和分配律。舉例來說，使用同餘可以讓13個數字的集合 $\{0,1,2,\cdots ,12\}$ 構成一個有限域。在這個域中，任何數學運算（加減乘除）都歸約成13的模，例如 $5\times 7=35{\bmod {1}}3=9$。對於任意素數$p$，都可以定義這種有限域；使用更複雜的方法，也可以對素數$p$的$m$次方定義這樣的有限域。有限域也叫做伽羅瓦域，其縮寫為 $\mathrm {GF} (P)$ 或$\mathrm {GF} (P^{m})$。

在這樣一個有$m$個數的域中，任何非零元素$a$都存在惟一乘法逆 $a^{-1}$使$aa^{-1}=a^{-1}a\equiv 1{\bmod {m}}$。這可以通過解同餘式$ax\equiv 1{\bmod {m}}$得出，或者也可以解與之等價的丟番圖方程

$ax+my=1$

這個方程可用擴展歐幾里得算法解出（參見上文）。在RSA算法中，尋找乘法逆是非常重要的一步，它決定了使用哪個數來解密信息。雖然RSA算法不使用域而是使用環，擴展歐幾里得算法仍然可以用來求乘法逆。歐幾里得算法也被應用於糾錯碼，例如，它可以代替伯利坎普－梅西算法解基於有限域的BCH碼和里德-所羅門碼。

中國剩餘定理

輾轉相除法也可以用來解線性丟番圖方程組。如在中國剩餘定理中，整數可以表示成被$N$個互素的數$m_{i}$除留下的餘數：

${\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}$如下：

$M_{i}={\frac {M}{m_{i}}}$

也就是，$M_{i}$是除了$m_{i}$以外所有模數的乘積。接着是關鍵的一步，尋找$N$個數$h_{i}$使：

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

有了這些數$h_{i}$之後，整數$x$可以用下式從餘數$x_{i}$中解出：

$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}$的乘法逆，所以可以使用擴展歐幾里得算法求出（見上一節）。

連分數

輾轉相除法和連分數有着緊密的關係。計算連分數的過程如下：

${\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}}$

其中每個式子的右邊最後一項都等於下一個式子的左邊項的倒數。所以前兩個式子可以組合成：

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

第三個式子可以代入分母中的${\frac {r_{1}}{r_{0}}}$：

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

每一步中，最後一項${\frac {r_{k}}{r_{k-1}}}$都可以用下一個式子代換，直至最後一個式子，結果是：

${\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，所以分數 ${\frac {1071}{462}}$ 可以寫成如下連分數形式：

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

整數分解算法

計算最大公約數是很多整數分解算法的重要步驟，如Pollard's rho算法、Shor算法、Dixon分解法以及Lenstra橢圓曲線分解。用輾轉相除法算最大公約數效率非常高。而連分數分解法由於用到了連分數，所以也需要使用輾轉相除法。

算法效率

用輾轉相除法求 GCD(x,y) 時所需的步數。紅點表示所需步驟較少（快），黃、綠、藍點所需步驟依次增加（慢）。

輾轉相除法的計算效率已經被徹底研究過了。一個算法的效率可以用計算所需步數乘以每步計算的開銷表示。加百利·拉梅於1884年指出，用輾轉相除法計算兩個數的最大公約數所需的步數不會超過其中較小數十進制下的位數$h$的5倍。因為每一步的計算開銷通常也是$h$數量級的，所以輾轉相除法的複雜度是$h^{2}$。

計算步數

計算兩個自然數$a$和$b$的最大公約數所需的步數可以表示為$T(a,b)$。如果$a$和$b$的最大公約數是$g$，$a=mg$，$b=ng$，而$m$和$n$是兩個互素整數，那麼：

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

這可以通過在輾轉相除法的計算過程中的每一步都除以$g$來證明。同樣，當$a$和$b$同時乘以$w$時，計算步數不變：$T(a,b)=T(wa,wb)$。所以，對於數值上相近的數，如$T(a,b)$和$T(a,b+1)$，計算步數可能相差很大。

根據輾轉相除法的遞歸性質可以得出另一個公式：

$T(a,b)=1+T(b,r_{0})=2+T(r_{0},r_{1})=\cdots =N+T(r_{N-2},r_{N-1})=N+1$

其中，根據定義有$T(x,0)=0$。

最差情況

假設用輾轉相除法求自然數$a$和$b$（$a>b>0$）的最大公約數需要$N$步，那麼滿足這一條件的$a$和$b$的最小值分別是斐波那契數$F_{N+2}$和$F_{N+1}$。這可以用數學歸納法證明。假設$N=1$，$b$整除$a$，滿足這一條件的$a$和$b$最小是$b=1$、$a=2$，正是$F_{2}$和$F_{3}$。現在假設這一規律對$M-1$有效。一個需要$M$步的算法的第一步是$a=q_{0}b+r_{0}$，第二步是$b=q_{1}r_{0}+r_{1}$。因為算法是遞歸的，它需要$M-1$步才能算出$\gcd(b,r_{0})$，其中$b$和$r_{0}$的最小值是$F_{M+1}$和$F_{M}$。所以$a$的最小值是當$q_{0}=1$的時候，此時 $q=b+r_{0}=F_{M+1}+F_{M}=F_{M+2}$。1844年，加百利·拉梅發現這個證明標誌着計算複雜性理論的誕生。這也是斐波那契數列的第一個實際應用。

這個結果也證明了輾轉相除法的運算步驟不會超過較小數十進制下的位數的五倍。因為如果算法需要$N$步，那麼$b$一定大於或等於$F_{N+1}$，也就是一定大於或等於$\varphi ^{N-1}$，其中$\varphi$是黃金分割比。因為$b\geq \varphi ^{N-1}$，所以$N-1\leq \log _{\varphi }b$。因為$\log _{10}\varphi >{\frac {1}{5}}$，${\frac {N-1}{5}}<\log _{10}\varphi \log _{\varphi }b=\log _{10}b$，所以$N\leq 5\log _{10}b$。所以，輾轉相除法不會進行超過O(h)次除法，其中$h$是較小數$b$在十進制下的位數。

平均情況

輾轉相除法的平均步驟數有三種不同的定義。第一種定義是計算已知自然數$a$和從0到$a-1$範圍內隨機選取的自然數$b$的最大公約數所需的時間$T(a)$：

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

但是因為$T(a,b)$在連續整數間變化非常劇烈，所以$T(a)$的值也會顯得很雜亂。

為了解決這個問題，第二種定義規定$\tau (a)$只要取遍其中所有和$a$互素的數即可：

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

在小於$a$的數中，有$\varphi (a)$個數與$a$互素，其中$\varphi$是歐拉函數。在這個定義中，$\tau (a)$的函數值增長得平穩很多。

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

誤差項的增長率為$O(a^{-{\frac {1}{6}}+\varepsilon })$，其中$\varepsilon$是無窮小量。公式中的常數$C$等於：

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

其中$\gamma$是歐拉-馬歇羅尼常數，$\zeta '$是黎曼ζ函數的導數。公式最左邊的${\frac {12}{\pi ^{2}}}\ln 2$由兩個獨立的方法確定。

因為第一種定義可以通過用第二種定義的求和來完成：

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

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

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

其中$\Lambda (d)$是馮·曼戈爾特函數。

第三種定義$Y(n)$定義為從1到$n$間隨機選取$a$和$b$（均勻分佈）時計算它們的最大公約數所需的平均步驟數：

$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)$的近似：

$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))，其中ℓ$l$是商的位數。

作為對比，輾轉相除法原先的版本使用的是減法，因此效率要慢很多。進行一次除法等同於進行$q$次減法（其中$q$是商）。如果$a$和$b$的比很大，計算出的商也很大，也就需要進行很多次減法。但在另一方面，計算出來的商在大多數情況下都是非常小的，除法中得出一個確定的商$q$的概率大約是$\log _{2}\left({\frac {u}{u-1}}\right)$。其中$u=(q+1)^{2}$。比如，商是1、2、3、4的可能性分別是大約41.5%、17.0%、9.3%、5.9%。因為計算機計算減法要快於除法，特別是對於很大的數字，所以減法版本的輾轉相除法的性能可以比得上除法版本。這也被運用於二進制最大公約數算法。

綜合考慮算法需要的步數和每一步的計算開銷，輾轉相除法隨兩個數字$a$和$b$的平均位數成平方級的速度增長（$h^{2}$）。設$h_{0},h_{1},\cdots ,h_{N-1}$表示計算過程中的餘數$r_{0},r_{1},\cdots ,r_{N-1}$的位數，因為算法的步數$N$隨$h$線性增長，所以算法的運算時間為：

$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$線性增長，也就是隨輸入數字的位數呈指數級增長。另一個很低效的算法是計算出兩個數的所有素因數（見上文），最大公約數等於所有公共素因數的乘積。但是整數分解算法效率極低，很多現代的加密系統甚至依靠這種低效率來防止資料被破解。

除了輾轉相除法之外，也有一些高效的算法存在，如二進制最大公約數算法將除法操作替換成了二進制的移位，以進一步提高用計算機運算時的效率。但是，這種改變並沒有降低算法的複雜度（仍然是O(h²)），雖然它在計算機上確實比輾轉相除法快些。也可以通過只檢視$a$和$b$的前幾位數來進一步提高效率，不過效果並不明顯。二進制版的算法還可以擴展到其它進制，效率最多可以提升五倍。

對於超過25,000位數的大數，有一種改進使算法複雜度降低至平方級以下，如Schönhage、Stehlé、Zimmermann等人提出的算法。這些算法利用2×2的矩陣（見上文）。這些亞平方級的算法複雜度通常是$O(h(\log h)^{2})(\log \log h)$。

其他數系

如上文所述，輾轉相除法最早用來尋找兩自然數的最大公約數，但其實它也可以被推廣至實數，甚至是多項式、二次整數和赫爾維茨四元數。在這些數系中，輾轉相除法甚至被用來證明一個重要特性：惟一分解，即這些數系中的數能夠被惟一地分解成不可約元素（素數在這些數系的對應物）。惟一分解是數論中很多證明的基礎。

有理數和實數

輾轉相除法可以被應用至實數，如歐幾里得在幾何原本第10卷中所說的那樣。算法的目的是計算出實數$g$，使已知實數$a$和$b$是它的整數倍：$a=mg$、$b=ng$，其中$m$和$n$是整數。這也就找到了$a$和$b$的整數關係，即找到整數$s$和$t$使$sa+tb=0$。歐幾里得使用輾轉相除法來處理不可通約的長度。

實數的輾轉相除法和整數的算法有兩個區別。第一，餘數$r_{k}$是實數，雖然商$q_{k}$仍然是整數。第二，算法不能保證在有限步內結束。如果能在有限步內結束，那麼分數${\frac {a}{b}}$是一個有理數，即：

${\frac {a}{b}}={\frac {mg}{ng}}={\frac {m}{n}}$

於是我們可以寫出它的有限連分數形式：$[q_{0};q_{1},q_{2},\cdots ,q_{n}]$。如果算法無法結束，那麼${\frac {a}{b}}$是無理數，可以寫成無限的連分數形式：$[q_{0};q_{1},q_{2},\cdots ]$。無限連分數的一個例子是：黃金分割比$\varphi =[1;1,1,\cdots ]$和2的算術平方根：${\sqrt {2}}=[1;2,2,\ldots ]$。通常，算法能夠結束的可能性是很低的，因為對於實數$a$和$b$，幾乎所有${\frac {a}{b}}$都是無理數。

如果算法不結束，也可以在第$k$步時終止計算，得到近似連分數$[q_{0};q_{1},q_{2},\cdots ,q_{k}]$。終止時的$k$越大，則近似越準確。連分數${\frac {m}{n}}$的分子和分母互素並滿足下式：

$m_{k}=q_{k}m_{k-1}+m_{k-2}$

$n_{k}=q_{k}n_{k-1}+n_{k-2}$

其中遞歸的初始值是$m_{-1}=n_{-2}=1$, $m_{-2}=n_{-1}=0$。${\frac {m_{k}}{n_{k}}}$是${\frac {a}{b}}$在分母是$n_{k}$的數中最精確的有理數近似值：

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

多項式

只含有一個變量$x$的多項式可以和整數一樣進行加法、乘法和分解為不可約多項式（也就是多項式中的「素數」）。兩個多項式$a(x)$和$b(x)$的最大公約數$g(x)$定義為它們分解之後共有的不可約因式的乘積，這可以用輾轉相除法進行計算。對於多項式的算法和整數的算法很相似，在每個步驟$k$，計算出滿足以下遞歸式的商多項式$q_{k}(x)$和餘數多項式$r_{k}(x)$：

$r_{k-2}(x)=q_{k}(x)r_{k-1}(x)+r_{k}(x)$

其中$r_{-2}(x)=a(x)$，$r_{-1}(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)$的最大公約數。

例如，有如下兩個四次多項式，都可以分解成兩個二次多項式的乘積：

$a(x)=x^{4}-4x^{3}+4x^{2}-3x+14=(x^{2}-5x+7)(x^{2}+x+2)$

和

$b(x)=x^{4}+8x^{3}+12x^{2}+17x+6=(x^{2}+7x+3)(x^{2}+x+2)$.

$a(x)$除以$b(x)$得到餘數：

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

在下一步中，$b(x)$除以$r_{0}(x)$得到$r_{1}(x)=x^{2}+x+2$。最終，$r_{0}(x)$除以$r_{1}(x)$得到的餘數為0，所以$r_{1}(x)$是$a(x)$和$b(x)$的最大公約數，這和它們因式分解的結果相符合。

上文所述的很多應用也適用於多項式。輾轉相除法可以解多項式的線性丟番圖方程和中國剩餘定理，也可以用來定義多項式的連分數展開式。

多項式的輾轉相除法也有其他應用，如施圖姆定理，一個用於計算多項式在給定區間內的實根個數的方法。這被應用於其他領域，如控制論的勞斯-赫爾維茨穩定性判據。

最後，多項式的係數不必局限於整數、實數、甚至複數。這些係數可以是其他域中的元素，如上文所述的有限域$\mathrm {GF} (p)$。從輾轉相除法得出的結論也可以直接推廣至這類多項式。

高斯整數

高斯素數u + vi在複平面的分布，其中u² + v²小於500。

高斯整數是滿足$\alpha =u+vi$的複數，其中$u$和$v$是普通整數，$i$是虛數單位（-1的平方根）。通過在高斯整數中定義輾轉相除法，根據上文貝祖等式可以證明高斯整數的惟一分解。高斯整數的惟一分解性質在很多應用中都很重要，如計算勾股數或者證明費馬平方和定理。輾轉相除法用於這些應用很方便，但並非必不可少，一些定理也可以由其他方式證明。

對於兩個高斯整數$\alpha$和$\beta$的輾轉相除法和普通整數只有兩個區別。像整數一樣，算法的第$k$步計算出商$q_{k}$和餘數$r_{k}$：

$r_{k}=r_{k-2}-q_{k}r_{k-1}$

其中$r_{k-2}=\alpha$，$r_{k-1}=\beta$，每個餘數都嚴格地小於前一個餘數，$|r_{k}|<|r_{k-1}|$。第一個區別即是：商和餘數都是高斯整數，也就是複數，所以商$q_{k}$是透過對實際比例（如複數$\alpha$/$\beta$）的實部和虛部取最近似整數來找出的。第二個區別就是需要定義複數比較大小的方法。所以我們定義一個範數函數$f(u+vi)=u^{2}+v^{2}$，以將高斯整數$u+vi$轉換成普通整數來比較大小。在每個步驟$k$中，餘數的範數${\ce {f(r_k)}}$必須小於前一個餘數的範數$f(r_{k-1})$。因為範數是非負整數並且在每一步都減小，所以輾轉相除法在有限步內一定能結束。最後一個非零餘數即是$\alpha$和$\beta$的最大公約數，即能同時整除$\alpha$和$\beta$的整數中範數最大的一個。若把乘以$\pm 1$或$\pm i$的所得結果考慮在內，那麼可以說$\alpha$和$\beta$的最大公約數是唯一的。

很多其他應用如線性丟番圖方程、中國剩餘定理都適用於高斯整數，高斯整數的連分數也可以用輾轉相除法定義。

歐幾里得整環

如果一個支持兩種二元運算（+ 和 ·）的元素的集合形成一個交換環R並且可以使用輾轉相除法求最大公約數，那麼這個集合叫做歐幾里得整環。這兩個二元運算不必是平常算數中的加法和乘法，它們可以是更廣泛的概念，如群或幺半群中的運算。但是這些運算仍然需要遵守交換律、結合律、分配律。

推廣之後的輾轉相除法需要一個歐幾里得函數，即一個將$R$映射到非負整數集合的函數$f$，使得對於$R$中非零元素$a$和$b$，$R$中存在$q$和$r$滿足$a=qb+r$，$f(r)<f(b)$。例如上文中用於高斯整數的範數函數。這個函數$f$可以是數的絕對值或模，也可以是多項式的次數，只要輾轉相除法計算過程中它的值不斷減小就行，這樣算法便能在有限步內結束。這非常依賴於非負整數的良序性，即每個非空的非負整數集合都有一個最小數。

任何歐幾里得整環都滿足算數基本定理：歐幾里得整環中的數可以惟一分解。所以任何歐幾里得整環都是惟一分解整環，但反之不然。歐幾里得整環是GCD整環（任意兩元素都存在最大公約數的整環）的子類。也就是說，在某些整環中，兩元素存在最大公約數但卻不能用輾轉相除法計算。歐幾里得整環都是主理想環，即其中每一個理想都是主理想，但並不是每個主理想環都是歐幾里得整環。

歐幾里得整環的惟一分解性質在很多場合都非常有用。例如，高斯整數的惟一分解性質可以方便地導出勾股數的公式，或者證明費馬平方和定理。惟一分解性質也是加百利·拉梅於1847年基於約瑟夫·劉維爾的建議發表的證明費馬最後定理的嘗試中的關鍵部分。拉梅的嘗試需要形如$x+\omega y$的數的惟一分解性質，其中$x$和$y$是整數，$\omega =e^{\frac {2i\pi }{n}}$是1的$n$次方根，即$\omega ^{n}=1$。雖然這對於某些$n$成立（如$n=3$時的艾森斯坦整數），但在其他情況下並非總是正確的。惟一分解性質在分圓域的失效使恩斯特·庫默爾發明了理想數的概念，隨後理查德·戴德金創造了理想的概念。

二次整數的惟一分解

艾森斯坦素數$u+v\omega$在複平面的分布（範數小於500，$\omega$等於1的立方根）。

二次整數環對於解釋歐幾里得整環很有幫助。二次整數是高斯整數的推廣，高斯整數中的虛數單位i被替換成一個複數ω。二次整數的形式是$u+v\omega$，其中$u$和$v$是整數，$\omega$有兩種形式，取決於參數$D$。如果$D$不等於四的倍數加一，那麼：

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

如果$D$等於四的倍數加一，那麼：

$\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時，二次整數環才是規範歐幾里德整環。$D=$ −1和−3時的二次整數分別叫作高斯整數和艾森斯坦整數。

但如果範數函數$f$可以是任何歐幾里得函數，那麼使二次整數環是歐幾里得整環的$D$的可能值到目前為止還不確定。是歐幾里得整環但不是規範歐幾里德整環的第一個例子（$D=69$）發表於1994年。溫伯格於1973年證明，在廣義黎曼猜想成立的前提下，$D>0$時的二次整數環是歐幾里得整環，當且僅當它是一個主理想環。

非交換環

輾轉相除法也可以應用至非交換環，如赫爾維茨四元數。令$\alpha$和$\beta$表示這樣一個環中的兩個元素。他們有右公約數$\delta$如果$\alpha =\xi \delta$, $\beta =\eta \delta$（$\xi$和$\eta$是環中的元素）。同樣，他們有左公約數$\delta$如果$\alpha =\delta \zeta$, $\beta =\delta \eta$（$\xi$和$\eta$是環中的元素）。因為乘法不符合交換律，也就有兩個版本的輾轉相除法，一個計算右公約數，一個計算左公約數。例如對於右公約數，輾轉相除法求最大公約數的第一步可以寫成：

$\rho _{0}=\alpha -\psi _{0}\beta =(\zeta -\psi _{0}\eta )\delta$

其中$\psi _{0}$是商，$\rho _{0}$是餘數。對於左公約數，第一步過程是：

$\rho _{0}=\alpha -\beta \psi _{0}=\delta (\zeta -\eta \psi _{0})$

不管是哪一種，這個過程都會重複到最大左公約數或者最大右公約數計算出，像在歐幾里得整環中一樣，$\rho _{0}$的「大小」一定小於$\beta$，並且對於$\rho _{0}$只有有限種的可能大小，這樣才能保證算法能夠結束。

由輾轉相除法得出的大多數結果都適用於非交換環。例如，貝祖等式表明最大右公約數可以表示成α的倍數和β的倍數的和，即，存在$\sigma$和$\tau$使：

$\Gamma _{\text{右 }}=\sigma \alpha +\tau \beta$

對於最大左公約數，等式如下：

$\Gamma _{\text{左 }}=\alpha \sigma +\beta \tau$

貝祖等式可以用來解非交換環的丟番圖方程。

推廣至其他數學結構

輾轉相除法可以推廣至紐結理論。

輾轉相除法有三個性質保證它不會永遠進行下去。第一，它可以寫成一系列遞歸式：

$r_{k}=r_{k-2}-q_{k}r_{k-1}$

其中每一個餘數都比前一個餘數小，$|r_{k}|<|r_{k-1}|$。第二，餘數的大小有嚴格下限，如$|r_{k}|\geq 0$。第三，小於$|r_{k}|$的數的數量是有限的。輾轉相除法推廣至其他數學結構，如纏結和超限序數時仍保持這種性質。

輾轉相除法的一個重要推廣是代數幾何中格羅布納基的概念。像前文所述，$a$和$b$的最大公約數$g$是它們的理想的生成元素。也就是說，對任何整數$s$和$t$，存在另一個整數$m$使：

$sa+tb=mg$

雖然這對一元多項式也成立，但是對多元多項式就不成立了。在多元多項式的情況下，生成元素的有限集合$g_{1},g_{2},\cdots$可以定義如下：

$sa+tb=\mathrm {\sum } _{k}m_{k}g_{k}$

其中$s$、$t$和$m_{k}$是多元多項式。任何這樣的多元多項式$f$可以表示成生成多項式的和加上惟一的餘數多項式$r$, 通常叫做多項式$f$的一般形式。

$f=r+\mathrm {\sum } _{k}q_{k}g_{k}$

雖然商多項式$q_{k}$可能不惟一。這些生成多項式的集合就叫做格羅布納基。

參考文獻

來源

書籍

• （英文）Cohen H. A Course in Computational Algebraic Number Theory. New York: Springer-Verlag. 1993 [2022-07-25]. ISBN 0-387-55640-0. （原始內容存檔於2019-05-03）. 
• （英文）Cohn H. Advanced Number Theory. New York: Dover. 1962 [2022-07-25]. ISBN 0-486-64023-X. （原始內容存檔於2019-05-02）. 
• （英文）Cormen TH, Leiserson CE, Rivest RL, and Stein C. Introduction to Algorithms 2nd. MIT Press and McGraw–Hill. 2001 [2022-07-25]. ISBN 0262032937. （原始內容存檔於2021-04-14）. 
• （英文）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 [2022-07-25]. ISBN 0-387-94680-2. （原始內容存檔於2019-05-02）. 
• （英文）狄利克雷. 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 [2022-07-25]. ISBN 0199219869. （原始內容存檔於2021-04-15）. 
• （英文）高德納. 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. 

外部連結

• Demonstrations of Euclid's algorithm （頁面存檔備份，存於網際網路檔案館）
• 埃里克·韋斯坦因. Euclidean Algorithm. MathWorld. 
• Euclid's Algorithm （頁面存檔備份，存於網際網路檔案館） at cut-the-knot
• Euclid's algorithm at PlanetMath.
• The Euclidean Algorithm Portuguese Web Archive的存檔，存檔日期2016-05-15 at MathPages
• Euclid's Game （頁面存檔備份，存於網際網路檔案館） at cut-the-knot
• Music and Euclid's algorithm （頁面存檔備份，存於網際網路檔案館）