輾轉相除法- 維基百科，自由的百科全書

最大公約數 輾轉相除法 維基百科，自由的百科全書 跳至導覽 跳至搜尋 輾轉相除法的演示動畫：兩條線段長分別可表示252和105，則其中每一小分段長代表最大公因數21。

如動畫所示，只要輾轉地從大數中減去小數，直到其中一段的長度為0，此時剩下的一條線段的長度就是252和105的最大公因數。

在數學中，輾轉相除法，又稱歐幾里得算法（英語：Euclideanalgorithm），是求最大公因數的算法。

輾轉相除法首次出現於歐幾里得的《幾何原本》（第VII卷，命題i和ii）中，而在中國則可以追溯至東漢出現的《九章算術》。

兩個整數的最大公因數是能夠同時整除它們的最大的正整數。

輾轉相除法基於如下原理：兩個整數的最大公因數等於其中較小的數和兩數相除餘數的最大公因數。

例如，252和105的最大公因數是21（ 252 = 21 × 12 ; 105 = 21 × 5 {\displaystyle252=21\times12;105=21\times5} ）；因為 252−105=21×(12−5)=147 ，所以147和105的最大公因數也是21。

在這個過程中，較大的數縮小了，所以繼續進行同樣的計算可以不斷縮小這兩個數直至餘數為零。

這時，所剩下的還沒有變成零的數就是兩數的最大公因數。

由輾轉相除法也可以推出，兩數的最大公因數可以用兩數的整數倍相加來表示，如 21=5×105+(−2)×252 。

這個重要的結論叫做貝祖定理。

輾轉相除法最早出現在歐幾里得的《幾何原本》中（大約公元前300年），所以它是現行的算法中歷史最悠久的。

這個算法原先只用來處理自然數和幾何長度（相當於正實數），但在19世紀，輾轉相除法被推廣至其他類型的數學對象，如高斯整數和一元多項式。

由此，引申出歐幾里得整環等等的一些現代抽象代數概念。

後來，輾轉相除法又擴展至其他數學領域，如紐結理論和多元多項式。

輾轉相除法有很多應用，它甚至可以用來生成全世界不同文化中的傳統音樂節奏。

[1]在現代密碼學方面，它是RSA算法（一種在電子商務中廣泛使用的公鑰加密算法）的重要部分。

它還被用來解丟番圖方程式，比如尋找滿足中國剩餘定理的數，或者求有限體中元素的逆。

輾轉相除法還可以用來構造連分數，在史特姆定理和一些整數分解算法中也有應用。

輾轉相除法是現代數論中的基本工具。

輾轉相除法處理大數時非常高效，如果用除法而不是減法實現，它需要的步驟不會超過較小數的位數（十進位下）的五倍。

拉梅於1844年證明了這點，同時這也標誌著計算複雜性理論的開端。

目次 1背景 1.1最大公約數 1.2歸納、遞歸和無窮遞降 2算法描述 2.1計算過程 2.2正確性的證明 2.3舉例 2.4圖形演示 2.5計算商和餘數 2.6計算機實現 2.7使用絕對值最小的餘數 3歷史發展 4數學上的應用 4.1貝祖等式 4.2主理想和相關問題 4.3擴展歐幾里得算法 4.4矩陣法 4.5歐幾里得引理和唯一分解 4.6線性丟番圖方程 4.7乘法逆和RSA算法 4.8中國剩餘定理 4.9連分數 4.10整數分解算法 5算法效率 5.1計算步數 5.1.1最差情況 5.1.2平均情況 5.2每一步的計算開銷 5.3其他算法的效率 6其他數系 6.1有理數和實數 6.2多項式 6.3高斯整數 6.4歐幾里得整環 6.4.1二次整數的惟一分解 6.5非交換環 7推廣至其他數學結構 8參考文獻 8.1引用 8.2來源 9外部連結 背景[編輯] 最大公因數[編輯] 歐幾里得的輾轉相除法計算的是兩個自然數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]首先證明定理對一個特定的數n0成立（通常是1）；然後證明如果定理對自然數n成立的話，那麼它對自然數n + 1成立。

這樣，便可證明定理對所有大於n0的自然數也成立。

遞迴[16]是將相關的數組成一個數列(a1, a2, a3...)，[17]當中除初始項外，其中每一項都用前一項或前幾項表示。

如費氏數列就是遞迴的，每一項Fn都等於Fn−1 + Fn−2（n≧2）。

輾轉相除法中的一些等式也是遞迴的。

最後，無窮遞降[18]是用方程式的一個自然數解導出比它小的自然數解。

[19]但是，這種轉化不能永遠進行下去，因為只有有限個小於原來的自然數解的自然數。

所以，要麼方程式無解，不然在有限步內必然能得出最小的自然數解。

在下文會用到此法來證明輾轉相除法一定會在有限步內結束。

算法描述[編輯] 計算過程[編輯] 輾轉相除法是一種遞迴算法，每一步計算的輸出值就是下一步計算時的輸入值。

[20]設k表示步驟數（從0開始計數），算法的計算過程如下。

每一步的輸入是都是前兩次計算的非負餘數rk−1和rk−2。

因為每一步計算出的餘數都在不斷減小，所以，rk−1小於rk−2。

在第k步中，算法計算出滿足以下等式的商qk和餘數rk： rk−2=qkrk−1+rk 其中0≤rk Option{ match(x,y){ (0,0)=>None, (a,0)=>Some(a.abs()), (muta,mutb)=>{ whileb!=0{ lett=b; b=a%b; a=t; } Some(a.abs()) }, } } Python3版本：defgcd(a,b): whileb!=0: t=a%b a=b b=t returna 在第k次循環開始時，變數b的值是前一次運算的餘數rk−1，變數a的值是再前一次運算的餘數rk−2。

步驟 b :=amodb 的作用等同於遞迴式 rk≡rk−2modrk−1 。

變數t的功能是在下一個餘數rk計算過程中臨時性地保存rk−1的值。

在一次循環結束時，變數b的值是前一次運算的餘數rk，變數a的值是再前一次運算的餘數rk−1。

在歐幾里得定義的減法版本，取餘運算被減法替換。

[27] functiongcd(a,b) ifa=0 returnb whileb≠0 ifa>b a←a−b else b←b−a returna 變數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。

以下是遞迴版本[28]： functiongcd(a,b) ifb=0 returna else returngcd(b,amodb) c++遞迴版本如下：intgcd(intn,intm) { returnm==0?n:gcd(m,n%m); } Rust遞迴版本：fngcd(x:isize,y:isize)->Option{ match(x,y){ (0,0)=>None, (a,0)=>Some(a.abs()), _=>gcd(y,x%y), } } Java版本：publicclassMethodOfSuccessiveDivision{ publicstaticvoidmain(String[]args){ System.out.println(gcd(1071,462)); } publicstaticintgcd(inta,intb){ if(b==0){ returna; }else{ returngcd(b,a%b); } } } Python3版本：defgcd(a,b): returnaifb==0elsegcd(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]取餘運算後，設rk是計算出的餘數（此時為正），q是計算出的商： rk−2=qkrk−1+rk 即假設rk−1 > rk > 0。

然後使用以下式子計算出一個負的餘數ek： rk−2=(qk+1)rk−1+ek 如果|ek|  0, y > 0)的話，那麼解的數量就可能是有限的。

有時候，這種對解的限制使丟番圖方程式在未知數個數比方程式數更多的情況下仍然能有唯一解[74]，而在允許實數解的線性方程組中，這種情況是不可能的。

乘法逆和RSA算法[編輯] 有限體是一個支持四種運算的數集。

這四種運算也通稱為加法、減法、乘法、除法，跟一般的四則運算有相同的性質，如交換律、結合律和分配律。

舉例來說，使用同餘可以讓13個數字的集合{0, 1, 2, …, 12}構成一個有限體。

在這個域中，任何數學運算（加減乘除）都歸約成13的模，例如5 × 7 = 35 mod 13 = 9。

對於任意質數p，都可以定義這種有限體；使用更複雜的方法，也可以對質數p的m次方定義這樣的有限體。

有限體也叫做伽羅瓦域，其縮寫為GF(p)或GF(p m)。

在這樣一個有m個數的域中，任何非零元素a都存在惟一乘法逆a−1使aa−1 = a−1a ≡ 1 mod m。

這可以通過解同餘式ax ≡ 1 mod m得出，[75]或者也可以解與之等價的丟番圖方程式[76] ax+my=1 這個方程式可用擴展歐幾里得算法解出（參見上文）。

在RSA算法中，尋找乘法逆是非常重要的一步，它決定了使用哪個數來解密訊息。

[77]雖然RSA算法不使用域而是使用環，擴展歐幾里得算法仍然可以用來求乘法逆。

歐幾里得算法也被應用於糾錯碼，例如，它可以代替伯利坎普－梅西算法解基於有限體的BCH碼和里德-所羅門碼。

[78] 中國剩餘定理[編輯] 輾轉相除法也可以用來解線性丟番圖方程組。

[79]如在中國剩餘定理中，整數可以表示成被N個互質的數mi除留下的餘數：[80] x 1 ≡ x ( mod m 1 ) x 2 ≡ x ( mod m 2 ) ⋮ x N ≡ x ( mod m N ) {\displaystyle{\begin{aligned}x_{1}&\equivx{\pmod{m_{1}}}\\x_{2}&\equivx{\pmod{m_{2}}}\\\vdots&\\x_{N}&\equivx{\pmod{m_{N}}}\end{aligned}}} 為了從x的N個餘數xi中確定x的值，我們將這些式子組合成單個線性丟番圖方程式，其中模數M是所有模數mi的乘積，然後定義Mi如下： M i = M / m i {\displaystyleM_{i}=M/m_{i}} 也就是，Mi是除了mi以外所有模數的乘積。

接著是關鍵的一步，尋找N個數hi使： M i h i ≡ 1 ( mod m i ) {\displaystyleM_{i}h_{i}\equiv1{\pmod{m_{i}}}} 有了這些數hi之後，整數x可以用下式從餘數xi中解出： x ≡ ( x 1 M 1 h 1 + x 2 M 2 h 2 + ⋯ + x N M N h N ) mod M {\displaystylex\equiv(x_{1}M_{1}h_{1}+x_{2}M_{2}h_{2}+\cdots+x_{N}M_{N}h_{N})\modM} 因為hi是Mi的乘法逆，所以可以使用擴展歐幾里得算法求出（見上一節）。

連分數[編輯] 輾轉相除法和連分數有著緊密的關係。

[81]計算連分數的過程如下： a b = q 0 + r 0 b b r 0 = q 1 + r 1 r 0 r 0 r 1 = q 2 + r 2 r 1 ⋮ r k − 2 r k − 1 = q k + r k r k − 1 ⋮ r N − 2 r N − 1 = q N {\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}}} 其中每個式子的右邊最後一項都等於下一個式子的左邊項的倒數。

所以前兩個式子可以組合成： a b = q 0 + 1 q 1 + r 1 r 0 {\displaystyle{\frac{a}{b}}=q_{0}+{\frac{1}{q_{1}+{\frac{r_{1}}{r_{0}}}}}} 第三個式子可以代入分母中的r1/r0： a b = q 0 + 1 q 1 + 1 q 2 + r 2 r 1 {\displaystyle{\frac{a}{b}}=q_{0}+{\frac{1}{q_{1}+{\frac{1}{q_{2}+{\frac{r_{2}}{r_{1}}}}}}}} 每一步中，最後一項rk/rk−1都可以用下一個式子代換，直至最後一個式子，結果是： a b = q 0 + 1 q 1 + 1 q 2 + 1 ⋱ + 1 q N = [ q 0 ; q 1 , q 2 , ⋯ , q N ] {\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)，其中商qk分別是2、3、7，所以分數1071/462可以寫成如下連分數形式： 1071 462 = 2 + 1 3 + 1 7 = [ 2 ; 3 , 7 ] {\displaystyle{\frac{1071}{462}}=2+{\frac{1}{3+{\frac{1}{7}}}}=[2;3,7]} 整數分解算法[編輯] 計算最大公因數是很多整數分解算法的重要步驟[82]，如Pollard'srho算法（英語：Pollard'srhoalgorithm）[83]、Shor算法[84]、Dixon分解法（英語：Dixon'sfactorizationmethod）[85]以及Lenstra橢圓曲線分解（英語：Lenstraellipticcurvefactorization）[86]。

用輾轉相除法算最大公因數效率非常高。

而連分數分解法由於用到了連分數，所以也需要使用輾轉相除法[87]。

算法效率[編輯] 用輾轉相除法求GCD(x,y)時所需的步數。

紅點表示所需步驟較少（快），黃、綠、藍點所需步驟依次增加（慢）。

輾轉相除法的計算效率已經被徹底研究過了。

[88]一個算法的效率可以用計算所需步數乘以每步計算的開銷表示。

加百利·拉梅於1884年指出[89]，用輾轉相除法計算兩個數的最大公因數所需的步數不會超過其中較小數十進制下的位數h的5倍。

[90][91]因為每一步的計算開銷通常也是h數量級的，所以輾轉相除法的複雜度是h2。

計算步數[編輯] 計算兩個自然數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,r0)=2+T(r0,r1)=…=N+T(rN−2,rN−1)=N+1 其中，根據定義有T(x,0) = 0。

[92] 最差情況[編輯] 假設用輾轉相除法求自然數a和b（a > b > 0）的最大公因數需要N步，那麼滿足這一條件的a和b的最小值分別是斐波那契數FN+2和FN+1。

[94]這可以用數學歸納法證明。

[95]假設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年，加百利·拉梅發現這個證明標誌著計算複雜性理論的誕生。

[96]這也是費氏數列的第一個實際應用。

[94] 這個結果也證明了輾轉相除法的運算步驟不會超過較小數十進位下的位數的五倍。

[97]因為如果算法需要N步，那麼b一定大於或等於FN+1，也就是一定大於或等於φN−1，其中φ是黃金分割比。

因為b ≥ φN−1，所以N − 1 ≤ logφb。

因為log10φ > 1/5，(N − 1)/5 0時的二次整數環是歐幾里得整環，若且唯若它是一個主理想環。

[136] 非交換環[編輯] 輾轉相除法也可以應用至非交換環，如赫爾維茨四元數。

[137]令α和β表示這樣一個環中的兩個元素。

他們有右公因數δ如果α = ξδ，β = ηδ（ξ和η是環中的元素）。

同樣，他們有左公因數δ如果α = δξ，β = δη（ξ和η是環中的元素）。

因為乘法不符合交換律，也就有兩個版本的輾轉相除法，一個計算右公因數，一個計算左公因數。

例如對於右公因數，輾轉相除法求最大公因數的第一步可以寫成： ρ0=α−ψ0β=(ξ−ψ0η)δ 其中ψ0是商，ρ0是餘數。

對於左公因數，第一步過程是： ρ0=α−βψ0=δ(ξ−ηψ0) 不管是哪一種，這個過程都會重複到最大左公因數或者最大右公因數計算出，像在歐幾里得整環中一樣，ρ0的「大小」一定小於β，並且對於ρ0只有有限種的可能大小，這樣才能保證算法能夠結束。

由輾轉相除法得出的大多數結果都適用於非交換環。

例如，貝祖等式表明最大右公因數可以表示成α的倍數和β的倍數的和，即，存在σ和τ使： Γ右=σα+τβ 對於最大左公因數，等式如下： Γ左=ασ+βτ 貝祖等式可以用來解非交換環的丟番圖方程式。

推廣至其他數學結構[編輯] 輾轉相除法可以推廣至紐結理論。

[138] 輾轉相除法有三個性質保證它不會永遠進行下去。

第一，它可以寫成一系列遞迴式： rk=rk−2−qkrk−1 其中每一個餘數都比前一個餘數小，|rk|