輾轉相除法

在數學中，輾轉相除法，又稱歐幾里得算法（英語：Euclidean algorithm），是求最大公因數的算法。輾轉相除法首次出現於歐幾里得的《幾何原本》（第VII卷，命題i和ii）中，而在中國則可以追溯至東漢出現的《九章算術》。
兩個整數的最大公因數是能夠同時整除它們的最大的正整數。輾轉相除法基於如下原理：兩個整數的最大公因數等於其中較小的數和兩數的差的最大公因數。例如，252和105的最大公因數是21（）；因為252 − 105 = 21 × (12 − 5) = 147
，所以147和105的最大公因數也是21。在這個過程中，較大的數縮小了，所以繼續進行同樣的計算可以不斷縮小這兩個數直至其中一個變成零。這時，所剩下的還沒有變成零的數就是兩數的最大公因數。由輾轉相除法也可以推出，兩數的最大公因數可以用兩數的整數倍相加來表示，如21 = 5 × 105 + (−2) × 252
。這個重要的結論叫做貝祖定理。 
輾轉相除法最早出現在歐幾里得的《幾何原本》中（大約公元前300年），所以它是現行的算法中歷史最悠久的。這個算法原先只用來處理自然數和幾何長度（相當於正實數），但在19世紀，輾轉相除法被推廣至其他類型的數學對象，如高斯整數和一元多項式。由此，引申出歐幾里得整環等等的一些現代抽象代數概念。後來，輾轉相除法又擴展至其他數學領域，如紐結理論和多元多項式。
輾轉相除法有很多應用，它甚至可以用來生成全世界不同文化中的傳統音樂節奏。在現代密碼學方面，它是RSA算法（一種在電子商務中廣泛使用的公鑰加密算法）的重要部分。它還被用來解丟番圖方程式，比如尋找滿足中國剩餘定理的數，或者求有限體中元素的逆。輾轉相除法還可以用來構造連分數，在史特姆定理和一些整數分解算法中也有應用。輾轉相除法是現代數論中的基本工具。
輾轉相除法處理大數時非常高效，如果用除法而不是減法實現，它需要的步驟不會超過較小數的位數（十進位下）的五倍。拉梅於1844年證明了這點，同時這也標誌著計算複雜性理論的開端。

歸納、遞迴和無窮遞降

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

圖形演示

輾轉相除法的計算過程可以用圖形演示。假設我們要在a×b的矩形地面上鋪正方形瓷磚，並且正好鋪滿，其中a大於b。我們先嘗試用b×b的瓷磚，但是留下了r₀×b的部分，其中r₀<b。我們接著嘗試用r₀×r₀的正方形瓷磚鋪，又留下了r₁×r₀的部分，然後再使用r₁×r₁的正方形鋪……直到全部鋪滿為止，即到某步時正方形剛好覆蓋剩餘的面積為止。此時用到的最小的正方形的邊長就是原來矩形的兩條邊長的最大公因數。在圖中，最小的正方形面積是21×21（紅色），而原先的矩形（綠色）邊長是1071×462，所以21是1071和462的最大公因數。

計算機實現

輾轉相除法可用偽代碼表示，比如除法版本可以寫成
function gcd(a, b)
    while b ≠ 0
        t ← b
        b ← a mod b
        a ← t
    return a

c++版本：
 1 int 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 }

Python3版本：
1 def gcd(a, b):2     while b != 0:3         t = a % b4         a = b5         b = t6     return a
在第k次循環開始時，變數b的值是前一次運算的餘數rₖ−1，變數a的值是再前一次運算的餘數rₖ−2。步驟
b := a mod b的作用等同於遞迴式
rₖ ≡ rₖ−2 mod rₖ−1。變數t的功能是在下一個餘數rₖ計算過程中臨時性地保存rₖ−1的值。在一次循環結束時，變數b的值是前一次運算的餘數rₖ，變數a的值是再前一次運算的餘數rₖ−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ₖ−1和rₖ−2。假定第k次循環開始時a大於b，那麼a等於rₖ−2，因為rₖ−2 > rₖ−1。在循環過程中，a重複減去b直到比b小，此時a就是下一個餘數rₖ；然後b重複減去a直到比a小，此時b就是下一個餘數rₖ₊₁；重複執行直到b = 0。
以下是遞迴版本：
function gcd(a, b)
    if b = 0
       return a
    else
       return gcd(b, a mod b)

c++遞迴版本如下：
1 int gcd(int n,int m)2 {3         if(m==0)4                 return n;5         else6                 return gcd(m,n%m);7 }

Python3版本：
1 def 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。

整數分解算法

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

算法效率

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

最差情況

假設用輾轉相除法求自然數a和b（a > b > 0）的最大公因數需要N步，那麼滿足這一條件的a和b的最小值分別是斐波那契數FN₊₂和FN₊₁。這可以用數學歸納法證明。假設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₀的最小值是 FM₊₁ 和 FM。所以a的最小值是當 q₀ = 1 的時候，此時 a = b + r₀ = FM₊₁ + FM = FM₊₂。1844年，加百利·拉梅發現這個證明標誌著計算複雜性理論的誕生。這也是費氏數列的第一個實際應用。
這個結果也證明了輾轉相除法的運算步驟不會超過較小數十進位下的位數的五倍。因為如果算法需要N步，那麼b一定大於或等於FN₊₁，也就是一定大於或等於φᴺ⁻¹，其中φ是黃金分割比。因為b ≥ φᴺ⁻¹，所以N − 1 ≤ logφb。因為log₁₀φ > 1/5，(N − 1)/5 < log₁₀φ logφb = log₁₀b，所以N ≤ 5 log₁₀b。所以，輾轉相除法不會進行超過O(h)次除法，其中h是較小數b在十進位下的位數。

其他算法的效率

因為輾轉相除法的高效率，它在實踐中被廣泛使用。作為對比，本段中介紹以下輾轉相除法以外的其他最大公因數算法的效率。
計算兩數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))。

其他數系

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

歐幾里得整環

如果一個支持兩種二元運算（+ 和 ·）的元素的集合形成一個交換環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時的艾森斯坦整數），但在其他情況下並非總是正確的。惟一分解性質在分圓體的失效使恩斯特·庫默爾發明了理想數的概念，隨後理察·戴德金創造了理想的概念。