輾轉相除法

在數學中，輾轉相除法，又稱歐幾里得演算法中，而在中國則可以追溯至東漢出現的《九章算術》。兩個整數的最大公約數是能夠同時整除它們的最大的正整數。輾轉相除法基於如下原理：兩個整數的最大公約數等於其中較小的數和兩數相除餘數的最大公約數。例如，252和105的最大公約數是21；因為formula_2，所以147和105的最大公約數也是21。在這個過程中，較大的數縮小了，所以繼續進行同樣的計算可以不斷縮小這兩個數直至餘數為零。這時，所剩下的還沒有變成零的數就是兩數的最大公約數。由輾轉相除法也可以推出，兩數的最大公約數可以用兩數的整數倍相加來表示，如formula_3。這個重要的結論叫做貝祖定理。輾轉相除法最早出現在歐幾里得的《幾何原本》中，但在19世紀，輾轉相除法被推廣至其他型別的數學物件，如高斯整數和一元多項式。由此，引申出歐幾里得整環等等的一些現代抽象代數概念。後來，輾轉相除法又擴充套件至其他數學領域，如紐結理論和多元多項式。輾轉相除法有很多應用，它甚至可以用來生成全世界不同文化中的傳統音樂節奏。在現代密碼學方面，它是RSA演算法的重要部分。它還被用來解丟番圖方程，比如尋找滿足中國剩餘定理的數，或者求有限域中元素的逆。輾轉相除法還可以用來構造連分數，在施圖姆定理和一些整數分解演算法中也有應用。輾轉相除法是現代數論中的基本工具。輾轉相除法處理大數時非常高效，如果用除法而不是減法實現，它需要的步驟不會超過較小數的位數的五倍。拉梅於1844年證明了這點，同時這也標誌著計算複雜性理論的開端。背景.最大公約數.歐幾里得的輾轉相除法計算的是兩個自然數formula_4和formula_5的最大公約數formula_6，意思是能夠同時整除formula_4和formula_5的自然數中最大的一個。兩個數的最大公約數通常寫成formula_9，或者簡寫成formula_10，但是第二種寫法也被使用在其他數學概念，如二維向量的座標。如果formula_11，則稱formula_4和formula_5互素。"a"和"b"是否互素和它們是否素數無關。如，6和35都不是素數，因為它們都可以分解為多於一個素因數的乘積：6 = 2 × 3，35 = 5 × 7。但是，6和35互素，因為除了1以外沒有自然數同時整除6和35。令formula_14。由於formula_4和formula_5都是"formula_6"的整數倍，所以可以寫成formula_18，並且不存在更大的整數formula_19使等式成立。為了使"formula_6"儘可能大，就要使formula_4和formula_5中所有公約數都提取出來歸入"formula_6"中，所以自然數formula_24和formula_25一定互素，並且formula_4和formula_5的最大公約數"formula_6"可以被formula_4和formula_5的所有其他公因數formula_31整除。我們可以用右圖來解釋最大公約數的概念：設一個長方形的邊長為formula_4和formula_5。因為formula_4和formula_5的任何公約數"formula_31"都可以整除formula_4和formula_5，所以長方形的邊都可以等分為長度為"formula_31"的線段，也就是長方形可以被邊長為"formula_31"的正方形正好填滿。而最大公約數"formula_6"是所有可能的"formula_31"中最大的一個。例如，一個24 × 60的長方形區域可以分成1 × 1、2 × 2、3 × 3、6 × 6或12 × 12的正方形網格。也就是說，12是24和60的最大公約數。formula_4和formula_5的最大公約數是兩數共有的素因數的乘積。例如，462可以分解成2 × 3 × 7 × 11；1071可以分解成3 × 3 × 7 × 17。462和1071的最大公約數等於它們共有的素因數的乘積3 × 7 = 21。如果兩數沒有公共的素因數，那麼它們的最大公約數是1，也即這兩個數互素。輾轉相除法的優點就在於它能以有系統的方式求出兩數的最大公約數，而無需分別對它們作因式分解。大數的素因數分解被認為是一個困難的問題，即使是現代的計算機也非常難於處理，所以許多加密系統的原理都是建基於此。在數學中，尤其是抽象代數的環論中，最大公約數有一個更加巧妙的定義：formula_4和formula_5的最大公約數"formula_6"是formula_4和formula_5的線性和中的最小正整數，即所有形如formula_50。用現代數學語言來說，formula_4和formula_5生成的理想即是由"formula_6"生成的主理想。最大公約數的這個定義和其他定義的等價性將在下面描述。三個數的最大公約數的定義和兩個數的相同，即是它們共有的素因數的積，它們或者也可以按下式計算：formula_60所以，歐幾里得的輾轉相除法實際可以計算任意多整數的最大公約數。歸納、遞迴和無窮遞降.下文的論證會用到三種相關的數學方法，分別是數學歸納法、遞迴和無窮遞降。數學歸納法經常用來證明某個定理對所有自然數成立：首先證明定理對一個特定的數formula_61成立。輾轉相除法中的一些等式也是遞迴的。最後，無窮遞降是用方程的一個自然數解匯出比它小的自然數解。但是，這種轉化不能永遠進行下去，因為只有有限個小於原來的自然數解的自然數。所以，要麼方程無解，不然在有限步內必然能得出最小的自然數解。在下文會用到此法來證明輾轉相除法一定會在有限步內結束。演算法描述.計算過程.輾轉相除法是一種遞迴演算法，每一步計算的輸出值就是下一步計算時的輸入值。設formula_69表示步驟數，演算法的計算過程如下。每一步的輸入是都是前兩次計算的非負餘數formula_70和formula_71。因為每一步計算出的餘數都在不斷減小，所以，formula_70小於formula_71。在第"formula_69"步中，演算法計算出滿足以下等式的商formula_75和餘數formula_76：formula_77其中formula_78。也就是formula_71要不斷減去formula_70直到比formula_70小。為求簡明，以下只說明如何求兩個非負整數formula_4和formula_5的最大公約數相除產生的商和餘數，以此類推。整個演算法可以用如下等式表示：如果有a，演算法的第一步實際上會把兩個數字交換，因為這時"formula_4"除以"formula_5"所得的商formula_95會等於0，餘數formula_92則等於formula_4。然後，演算法的第二步便是把"formula_5"除以"formula_4"，再計算所得之商和餘數。所以，對於formula_100總有formula_101，即運算的每一步中得出的餘數一定小於上一步計算的餘數。由於每一步的餘數都在減小並且不為負數，必然存在第formula_25步時formula_103等於0，使演算法終止，formula_104就是"formula_4"和"formula_5"的最大公約數。其中"formula_25"不可能無窮大，因為在formula_92和0之間只有有限個自然數。正確性的證明.輾轉相除法的正確性可以分成兩步來證明。在第一步，我們會證明演算法的最終結果formula_104同時整除"formula_4"和"formula_5"。因為它是一個公約數，所以必然小於或者等於最大公約數formula_6。在第二步，我們證明"formula_6"能整除formula_104。所以"formula_6"一定小於或等於formula_104。兩個不等式只在formula_117時同時成立。具體證明如下：舉例.例如，計算formula_155和formula_156的最大公約數的過程如下：從1071中不斷減去462直到小於462，餘數是147：formula_158然後從462中不斷減去147直到小於147，餘數是21：formula_160再從147中不斷減去21直到小於21，沒有餘數：formula_162此時，餘數是0，所以1071和462的最大公約數是21，這和用素因數分解得出的結果相同用表格表示如下：圖形演示.輾轉相除法的計算過程可以用圖形演示。假設我們要在formula_163的矩形地面上鋪正方形瓷磚，並且正好鋪滿，其中formula_4大於formula_5。我們先嚐試用formula_166的瓷磚，但是留下了formula_167的部分，其中formula_168的正方形瓷磚鋪，又留下了formula_169的部分，然後再使用formula_170的正方形鋪……直到全部鋪滿為止，即到某步時正方形剛好覆蓋剩餘的面積為止。此時用到的最小的正方形的邊長就是原來矩形的兩條邊長的最大公約數。在圖中，最小的正方形面積是21×21邊長是1071×462，所以21是1071和462的最大公約數。計算商和餘數.在每個步驟formula_69中，輾轉相除法都需要計算兩個數formula_70和formula_71的商formula_75和餘數formula_76：formula_77其中formula_177。除法的演算法保證這樣的商和餘數總是存在。自然數的除法演算法還指出這樣的商和餘數是惟一的，但這對輾轉相除法而言並非必要。在歐幾里得最初的描述中，商和餘數是透過連續的減法來計算的，即從formula_71中不斷減去formula_70直到小於formula_70。一個更高效的做法是使用整數除法和模除來計算商和餘數：formula_181計算機實現.輾轉相除法可用偽程式碼表示，比如除法版本可以寫成function gcd(a, b)while b ≠ 0t ← bb ← a mod ba ← treturn aC++版本：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) -&gt; Option {match (x,y) {(0, 0) =&gt; None,(a, 0) =&gt; Some(a.abs()),(mut a, mut b) =&gt; {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 % ba = bb = treturn a在第formula_69次迴圈開始時，變數formula_5的值是前一次運算的餘數formula_70，變數formula_4的值是再前一次運算的餘數formula_71。步驟formula_187的作用等同於遞迴式formula_181。變數formula_189的功能是在下一個餘數formula_76計算過程中臨時性地儲存formula_70的值。在一次迴圈結束時，變數"formula_5"的值是前一次運算的餘數"formula_76"，變數"formula_4"的值是再前一次運算的餘數formula_70。在歐幾里得定義的減法版本，取餘運算被減法替換。function gcd(a, b)if a = 0return bwhile b ≠ 0if a &gt; ba ← a − belseb ← b − areturn a變數"formula_4"和"formula_5"的值分別是前兩次的餘數formula_70和formula_71。假定第"formula_69"次迴圈開始時"formula_4"大於"formula_5"，那麼"formula_4"等於formula_71，因為formula_205。在迴圈過程中，"formula_4"重複減去"formula_5"直到比"formula_5"小，此時"formula_4"就是下一個餘數"formula_76"；然後"formula_5"重複減去"formula_4"直到比"formula_4"小，此時"formula_5"就是下一個餘數formula_215；重複執行直到formula_216。以下是遞迴版本：function gcd(a, b)if b = 0return aelsereturn 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) -&gt; Option {match (x,y) {(0, 0) =&gt; None,(a, 0) =&gt; Some(a.abs()),_ =&gt; 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)例如formula_217的計算過程是：函式的第一次呼叫計算formula_218；下一次呼叫計算formula_219，在接下來是formula_220。使用絕對值最小的餘數.在另一個版本的演算法中，每一步還要把取餘運算時計算出的商增加一後再重新計算餘數，formula_222是計算出的商：formula_77即假設formula_224。然後使用以下式子計算出一個負的餘數formula_225：formula_226如果formula_227，那麼用"formula_225"替換"formula_76"進行下一次運算。如利奧波德·克羅內克所指出的，這個版本需要的運算步驟是歐幾里得演算法的所有版本中最少的。歷史發展.輾轉相除法是目前仍然在使用的歷史最悠久的演算法之一。它首次出現於《幾何原本》。卷10中出現的演算法是幾何的，兩段線段"a"和"b"的最大公約數是"a"和"b"的公度中的最大值。這個演算法可能並非歐幾里得發明，因為他也有將先前其他數學家的一些成果編進他的《幾何原本》。數學家、歷史學家認為卷7的內容可能來自畢達哥拉斯學院出身的數學家寫的關於數論的教科書。輾轉相除法在當時很可能已為尤得塞斯所知，甚至可能更早之前就已經存在，因為歐幾里得和亞里士多德的著作中都出現了--一詞。幾個世紀之後，輾轉相除法又分別被中國人和印度人獨立發現，主要用來解天文學中用到的丟番圖方程以及制定準確的歷法。5世紀末，印度數學家、天文學家阿里亞哈塔曾稱輾轉相除法為“粉碎機”，這可能是因為它在解丟番圖方程時很有效。在中國，《九章算術》中提到了一種類似輾轉相減法的“更相減損術”。《孫子算經》中則出現了中國剩餘定理的一個特例，但是直到1247年秦九韶才於其《數學九章》中解答了該定理的一般情況，當中用到了他發明的大衍求一術。此法的其中一部分實際上便是輾轉相除的原理，秦九韶在書中對此有明確表述。在歐洲，輾轉相除法首次出現於的著作《愉悅討喜的問題》的第二版在歐洲，輾轉相除法被用於丟番圖方程和構建連分數。後來，英國數學家在其著作中收編了擴充套件歐幾里得演算法，作為一個有效計算連分數的方法。他將此法的名於。19世紀，輾轉相除法促成了新數系的建立，如高斯整數和艾森斯坦整數。1815年，高斯用輾轉相除法證明高斯整數的分解是惟一的，儘管他的研究到了1832年才首度發表。高斯在他的《算數研究》中實際上也有援引這個演算法，但僅是以連分數方法的形式敘述。約翰·狄利克雷是第一個將輾轉相除法作為數論的基礎的數學家。#重定向輾轉相除法的其他應用發展於19世紀。1829年，施圖姆將輾轉相除法用於施圖姆序列。輾轉相除法是歷史上第一個，即尋找兩個可通約實數的整數關係的演算法。近年來，出現了一些新穎的整數關係演算法，如和福爾卡德於1979年發表的弗格森-福爾卡德演算法、以及與它相關的、HJLS演算法以及PSLQ演算法。1969年，科爾基於輾轉相除法創造了一種二人遊戲，叫做「歐幾里得遊戲」。這個遊戲有最優策略。遊戲開始於兩列分別為"a"和"b"個棋子組成的序列，玩家輪流從較長一列中取走較短一列棋子數量的"m"倍的棋子。如果兩列棋子"p"和"q"分別由"x"和"y"個棋子組成，其中"x"大於"y"，那麼玩家可以將序列"p"的棋子數量減少為自然數"x" − "my"。最後率先將一列棋子清空的玩家勝出。數學上的應用.貝祖等式.貝祖等式說明，兩個數formula_4和formula_5的最大公約數formula_6可以表示為formula_4和formula_5的線性和。也就是說，存在整數formula_235和formula_189使formula_237。整數formula_235和formula_189可以從輾轉相除法算出的商formula_240計算出。 從輾轉相除法的最後一步開始，"formula_6"可以表示成前一步的商formula_242和前兩步的餘數formula_243和formula_244：formula_245而前兩步的餘數又分別可以表示成它們前兩步的餘數和商：formula_246formula_247將這兩行式子先後代入第一個式子，可以將formula_6表示成formula_249和formula_250的線性和。重複進行迭代直到出現formula_4和formula_5：formula_253formula_254formula_255最終，"g"可以表示成formula_4和formula_5的線性和：formula_237。貝祖等式以及以上證明都可以擴充套件至歐幾里得整環。主理想和相關問題.貝祖等式提供了另一種定義formula_4和formula_5的最大公約數"formula_6"的方法。考慮形如formula_50的數的集合。因為formula_4和formula_5都可以被"formula_6"整除，所以這個集合中的所有元素都可以被"formula_6"整除。也就是說這個集合中的數都可以表示成"formula_6"的倍數，或者formula_4和formula_5的其他公約數的倍數。但是，只有最大公約數才是這個集合的元素。根據貝祖等式，有formula_237。換言之，當formula_273、formula_274時得出"formula_6"。任何其他的公約數都不是這個集合的元素，因為它們都不能被比它們大的"formula_6"整除。相反地，"formula_6"的任何倍數都屬於這個集合，只要令formula_278、formula_279，便有：formula_280所以，形如formula_50的數的集合等於"formula_6"的整數倍的集合。也就是說，任意兩個數的線性和的集合等同於它們最大公約數的整數倍的集合。formula_4和formula_5的最大公約數叫做formula_4和formula_5的理想的生成元素。這個最大公約數的定義匯出了兩個現代抽象代數的概念：主理想。這個結果可以解決某些實際問題。例如，考慮兩個容積分別為formula_4和formula_5的量杯，其中formula_4和formula_5為正整數。透過加入或倒去"formula_51"倍第一個量杯的體積以及"formula_52"倍第二個量杯的體積的液體，任何體積為formula_50的液體都可以被量出。根據貝祖等式，凡是可以被量出的液體，其體積一定是formula_4和formula_5的最大公約數"formula_6"的倍數。擴充套件歐幾里得演算法.貝祖等式的整數"s"和"t"可以透過擴充套件歐幾里得演算法算出。這個擴充套件演算法在原有輾轉相除法的基礎上增加了兩個遞迴等式：formula_298formula_299演算法開始時：formula_300, formula_301formula_302, formula_303加上這兩個遞迴式後，當演算法終止於formula_304，貝祖等式的整數formula_235和formula_189分別由formula_307和formula_308給出。這個演算法的正確性可以用數學歸納法來證明。假設遞迴至第formula_309步是正確的，也就是假設：formula_310在formula_311小於formula_69時皆成立。則第"formula_69"步運算得出以下等式：formula_314因為formula_71和formula_70被假定是正確的，所以可以用formula_235和formula_189表示：formula_319整理後得到第"formula_69"步的結果，和我們期望得到的結果一致：formula_321矩陣法.整數formula_235和formula_189也可以用矩陣運算得出。輾轉相除法的計算過程：formula_324formula_325formula_326可以寫作2×2的商矩陣乘以一個2維餘數向量：formula_327令formula_328表示所有商矩陣的乘積：formula_329這使輾轉相除法化簡為：formula_330如要用formula_4和formula_5的線性和表示formula_6，可將等式兩邊同時乘以矩陣formula_328的逆矩陣。formula_328的行列式等於formula_336，因為它等於商矩陣的行列式的乘積，而每一個的行列式都是−1。因為formula_328的行列式不為零，最終的餘數向量可以利用formula_328的逆矩陣解出：formula_339由上式可以得出formula_340。貝祖等式中的兩個整數分別是formula_341、formula_342。矩陣法的效率可前文描述的輾轉相除法的遞迴演算法是相同的，每一步都有兩次乘法和兩次加法。歐幾里得引理和唯一分解.貝祖等式對輾轉相除法的很多應用都很重要，如證明自然數的唯一分解性質假設數字"L"可以寫成兩個因數formula_51和formula_52的乘積，即formula_345。如果另一個數formula_346與formula_51互素的數也能整除formula_348，那麼"formula_346"必須整除"formula_52"，證明如下：如果"formula_51"和"formula_346"的最大公約數是1，則根據貝祖等式存在formula_235和formula_189使formula_355。兩邊都乘以"formula_52"：formula_357因為"formula_346"整除等式右邊，所以也應整除等式左邊的"formula_52"。這個結果叫做歐幾里得引理。如果一個素數整除"formula_348"那麼它至少整除"formula_348"的一個因數。如果一個數"formula_346"互素於數列formula_363 中的每一個數，則"w"也一定互素於它們的乘積formula_364。歐幾里得引理足以證明每一個自然數的素數分解是惟一的。我們用反證法來證明，假設"formula_348"可以分別分解成formula_24個素數和formula_25個素數，即：formula_368根據假設，每個素數formula_369都能整除"formula_348"，因此它必須能夠整除某個formula_222；因為"formula_222"也是一個素數，所以formula_373。同理，對於每一個"formula_369"都存在一個"formula_222"與它相等。所以兩種分解除了順序不同以外是完全相同的。整數分解的惟一性在數學證明中有很多應用，下文將會提到。線性丟番圖方程.丟番圖方程是以亞歷山大數學家丟番圖的名字命名的一類方程，它的解被限制在整數範圍。關於整數formula_376和formula_377的線性丟番圖方程形如：formula_378其中formula_4、formula_5、formula_31是已知整數。這個方程可以寫成關於"formula_376"的同餘式：formula_383令formula_6為"formula_4"和"formula_5"的最大公約數，formula_4、formula_5都能被formula_6整除，故formula_390能夠被"formula_6"整除。所以，"formula_31"一定能夠被"formula_6"整除，不然方程就無解。方程兩邊若同時除以 formula_394，方程就變成了貝祖等式：formula_395其中formula_235和formula_189可以用擴充套件歐幾里得演算法求解。所以這個丟番圖方程的一個解即是：formula_398總體而言，丟番圖方程如果有解，就一定有無數個解。只需要考慮兩個解formula_399 和formula_400：formula_401或者可以寫成：formula_402所以相鄰兩個解的"formula_376"之間的差是formula_404，"formula_377"之間的差是formula_406。這樣，所有的解都可以表示成：formula_407當formula_408取遍所有整數時，方程所有的解都可以從formula_399計算出來。如果限制為正整數解 (formula_410, formula_411) 的話，那麼解的數量就可能是有限的。有時候，這種對解的限制使丟番圖方程在未知數個數比方程數更多的情況下仍然能有唯一解，而在允許實數解的線性方程組中，這種情況是不可能的。乘法逆和RSA演算法.有限域是一個支援四種運算的數集。這四種運算也通稱為加法、減法、乘法、除法，跟一般的四則運算有相同的性質，如交換律、結合律和分配律。舉例來說，使用同餘可以讓13個數字的集合 formula_412 構成一個有限域。在這個域中，任何數學運算都歸約成13的模，例如 formula_413。對於任意素數formula_414，都可以定義這種有限域；使用更復雜的方法，也可以對素數"formula_414"的formula_416次方定義這樣的有限域。有限域也叫做伽羅瓦域，其縮寫為 formula_417 或formula_418。在這樣一個有"formula_416"個數的域中，任何非零元素formula_420都存在惟一乘法逆 formula_421使formula_422。這可以透過解同餘式formula_423得出，或者也可以解與之等價的丟番圖方程formula_424這個方程可用擴充套件歐幾里得演算法解出。在RSA演算法中，尋找乘法逆是非常重要的一步，它決定了使用哪個數來解密資訊。雖然RSA演算法不使用域而是使用環，擴充套件歐幾里得演算法仍然可以用來求乘法逆。歐幾里得演算法也被應用於糾錯碼，例如，它可以代替伯利坎普－梅西演算法解基於有限域的BCH碼和裡德-所羅門碼。中國剩餘定理.輾轉相除法也可以用來解線性丟番圖方程組。如在中國剩餘定理中，整數可以表示成被formula_425個互素的數formula_426除留下的餘數：formula_427為了從formula_428的"formula_425"個餘數formula_430中確定"formula_428"的值，我們將這些式子組合成單個線性丟番圖方程，其中模數formula_432是所有模數"formula_426"的乘積，然後定義formula_434如下：formula_435也就是，"formula_434"是除了"formula_426"以外所有模數的乘積。接著是關鍵的一步，尋找"formula_425"個數formula_439使：formula_440有了這些數"formula_439"之後，整數"formula_428"可以用下式從餘數formula_430中解出：formula_444因為"formula_439"是"formula_434"的乘法逆，所以可以使用擴充套件歐幾里得演算法求出。連分數.輾轉相除法和連分數有著緊密的關係。計算連分數的過程如下：formula_447其中每個式子的右邊最後一項都等於下一個式子的左邊項的倒數。所以前兩個式子可以組合成：formula_448第三個式子可以代入分母中的formula_449：formula_450每一步中，最後一項formula_451都可以用下一個式子代換，直至最後一個式子，結果是：formula_452在上文的例子中計算了formula_453，其中商formula_454分別是2、3、7，所以分數 formula_455 可以寫成如下連分數形式：formula_456整數分解演算法.計算最大公約數是很多整數分解演算法的重要步驟，如、Shor演算法、以及。用輾轉相除法算最大公約數效率非常高。而連分數分解法由於用到了連分數，所以也需要使用輾轉相除法。演算法效率.輾轉相除法的計算效率已經被徹底研究過了。一個演算法的效率可以用計算所需步數乘以每步計算的開銷表示。加百利·拉梅於1884年指出，用輾轉相除法計算兩個數的最大公約數所需的步數不會超過其中較小數十進位制下的位數formula_457的5倍。因為每一步的計算開銷通常也是"formula_457"數量級的，所以輾轉相除法的複雜度是formula_459。計算步數.計算兩個自然數formula_460和formula_461的最大公約數所需的步數可以表示為formula_462。如果formula_460和formula_461的最大公約數是formula_465，formula_466，formula_467，而formula_468和formula_469是兩個互素整數，那麼：formula_470這可以透過在輾轉相除法的計算過程中的每一步都除以"formula_465"來證明。同樣，當formula_460和formula_461同時乘以formula_474時，計算步數不變：formula_475。所以，對於數值上相近的數，如formula_462和formula_477，計算步數可能相差很大。根據輾轉相除法的遞迴性質可以得出另一個公式：formula_478其中，根據定義有formula_479。最差情況.假設用輾轉相除法求自然數formula_460和formula_461的最大公約數需要formula_483步，那麼滿足這一條件的formula_460和formula_461的最小值分別是斐波那契數formula_486和formula_487。這可以用數學歸納法證明。假設formula_488，"formula_461"整除"formula_460"，滿足這一條件的formula_460和formula_461最小是formula_493、formula_494，正是formula_495和formula_496。現在假設這一規律對formula_497有效。一個需要formula_498步的演算法的第一步是formula_499，第二步是formula_500。因為演算法是遞迴的，它需要formula_497步才能算出formula_502，其中formula_461和formula_504的最小值是formula_505和formula_506。所以"formula_460"的最小值是當formula_508的時候，此時 formula_509。1844年，加百利·拉梅發現這個證明標誌著計算複雜性理論的誕生。這也是斐波那契數列的第一個實際應用。這個結果也證明了輾轉相除法的運算步驟不會超過較小數十進位制下的位數的五倍。因為如果演算法需要"formula_483"步，那麼"formula_461"一定大於或等於formula_487，也就是一定大於或等於formula_513，其中formula_514是黃金分割比。因為formula_515，所以formula_516。因為formula_517，formula_518，所以formula_519。所以，輾轉相除法不會進行超過"O"("h")次除法，其中formula_457是較小數formula_461在十進位制下的位數。平均情況.輾轉相除法的平均步驟數有三種不同的定義。第一種定義是計算已知自然數formula_460和從0到formula_523範圍內隨機選取的自然數"formula_461"的最大公約數所需的時間formula_525：但是因為formula_462在連續整數間變化非常劇烈，所以formula_525的值也會顯得很雜亂。為了解決這個問題，第二種定義規定formula_528只要取遍其中所有和"formula_460"互素的數即可：在小於"formula_460"的數中，有formula_531個數與"formula_460"互素，其中formula_514是尤拉函式。在這個定義中，formula_528的函式值增長得平穩很多。formula_535誤差項的增長率為formula_536，其中formula_537是無窮小量。公式中的常數formula_538等於：formula_539其中formula_540是尤拉-馬歇羅尼常數，formula_541是黎曼ζ函式的導數。公式最左邊的formula_542由兩個獨立的方法確定。因為第一種定義可以透過用第二種定義的求和來完成：formula_543所以也可以由以下公式近似：formula_544其中formula_545是馮·曼戈爾特函式。第三種定義formula_546定義為從1到formula_469間隨機選取formula_460和formula_461時計算它們的最大公約數所需的平均步驟數：formula_550將formula_525的近似公式代入，得到formula_546的近似：formula_553每一步的計算開銷.在輾轉相除法的每一步中，商formula_454和餘數formula_555都透過formula_556和formula_557求出：formula_558所以每一步的計算開銷主要與計算商"formula_454"的演算法有關，因為餘數"formula_555"可以很迅速地從formula_556、formula_557和"formula_454"計算出來：formula_564而計算一個formula_457位整數的除法的演算法複雜度是"O"("h"("ℓ"+1))，其中"ℓ"formula_566是商的位數。作為對比，輾轉相除法原先的版本使用的是減法，因此效率要慢很多。進行一次除法等同於進行formula_567次減法。如果formula_460和formula_461的比很大，計算出的商也很大，也就需要進行很多次減法。但在另一方面，計算出來的商在大多數情況下都是非常小的，除法中得出一個確定的商"formula_567"的機率大約是formula_572。其中formula_573。比如，商是1、2、3、4的可能性分別是大約41.5%、17.0%、9.3%、5.9%。因為計算機計算減法要快於除法，特別是對於很大的數字，所以減法版本的輾轉相除法的效能可以比得上除法版本。這也被運用於二進位制最大公約數演算法。綜合考慮演算法需要的步數和每一步的計算開銷，輾轉相除法隨兩個數字formula_460和formula_461的平均位數成平方級的速度增長。設formula_577表示計算過程中的餘數formula_578的位數，因為演算法的步數formula_483隨formula_457線性增長，所以演算法的運算時間為：formula_581其他演算法的效率.因為輾轉相除法的高效率，它在實踐中被廣泛使用。作為對比，本段中介紹以下輾轉相除法以外的其他最大公約數演算法的效率。計算兩數formula_460和formula_461的最大公約數有一個效率很慢的演算法：將"formula_460"除以從2到"formula_461"之間的每一個整數以計算出它們所有的公約數，其中最大的一個即是最大公約數。在這個演算法中，步驟數隨"formula_461"線性增長，也就是隨輸入數字的位數呈指數級增長。另一個很低效的演算法是計算出兩個數的所有素因數，最大公約數等於所有公共素因數的乘積。但是整數分解演算法效率極低，很多現代的加密系統甚至依靠這種低效率來防止資料被破解。除了輾轉相除法之外，也有一些高效的演算法存在，如二進位制最大公約數演算法將除法操作替換成了二進位制的移位，以進一步提高用計算機運算時的效率。但是，這種改變並沒有降低演算法的複雜度，雖然它在計算機上確實比輾轉相除法快些。也可以透過只檢視formula_460和formula_461的前幾位數來進一步提高效率，不過效果並不明顯。二進位制版的演算法還可以擴充套件到其它進位制，效率最多可以提升五倍。對於超過25,000位數的大數，有一種改進使演算法複雜度降低至平方級以下，如Schönhage、Stehlé、Zimmermann等人提出的演算法。這些演算法利用2×2的矩陣。這些亞平方級的演算法複雜度通常是formula_589。其他數系.如上文所述，輾轉相除法最早用來尋找兩自然數的最大公約數，但其實它也可以被推廣至實數，甚至是多項式、二次整數和赫爾維茨四元數。在這些數系中，輾轉相除法甚至被用來證明一個重要特性：惟一分解，即這些數系中的數能夠被惟一地分解成不可約元素。惟一分解是數論中很多證明的基礎。有理數和實數.輾轉相除法可以被應用至實數，如歐幾里得在幾何原本第10卷中所說的那樣。演算法的目的是計算出實數formula_465，使已知實數formula_460和formula_461是它的整數倍：formula_466、formula_467，其中formula_468和formula_469是整數。這也就找到了formula_460和formula_461的整數關係，即找到整數formula_599和formula_600使formula_601。歐幾里得使用輾轉相除法來處理不可通約的長度。實數的輾轉相除法和整數的演算法有兩個區別。第一，餘數formula_555是實數，雖然商formula_454仍然是整數。第二，演算法不能保證在有限步內結束。如果能在有限步內結束，那麼分數formula_604是一個有理數，即：formula_605於是我們可以寫出它的有限連分數形式：formula_606。如果演算法無法結束，那麼formula_604是無理數，可以寫成無限的連分數形式：formula_608。無限連分數的一個例子是：黃金分割比formula_609和2的算術平方根：。通常，演算法能夠結束的可能性是很低的，因為對於實數formula_460和formula_461，幾乎所有formula_604都是無理數。如果演算法不結束，也可以在第formula_69步時終止計算，得到近似連分數formula_614。終止時的"formula_69"越大，則近似越準確。連分數formula_616的分子和分母互素並滿足下式：formula_617formula_618其中遞迴的初始值是formula_619, formula_620。formula_621是formula_604在分母是formula_623的數中最精確的有理數近似值：formula_624多項式.只含有一個變數formula_625的多項式可以和整數一樣進行加法、乘法和分解為不可約多項式。兩個多項式formula_626和formula_627的最大公約數formula_628定義為它們分解之後共有的不可約因式的乘積，這可以用輾轉相除法進行計算。對於多項式的演算法和整數的演算法很相似，在每個步驟"formula_69"，計算出滿足以下遞迴式的商多項式formula_630和餘數多項式formula_631：formula_632其中formula_633，formula_634。所選擇的商式必須能使formula_635的首項系數和formula_636的相等，這樣才能保證每個餘數的次數小於前一個餘數。因為非零多項式的次數是非負整數，並且在每一步都減小，所以輾轉相除法的計算一定能在有限步內結束。最後一個非零餘數即是兩個多項式formula_626和formula_627的最大公約數。例如，有如下兩個四次多項式，都可以分解成兩個二次多項式的乘積：formula_640和formula_641.formula_626除以formula_627得到餘數：formula_644在下一步中，formula_627除以formula_646得到formula_647。最終，formula_646除以formula_649得到的餘數為0，所以formula_649是formula_626和formula_627的最大公約數，這和它們因式分解的結果相符合。上文所述的很多應用也適用於多項式。輾轉相除法可以解多項式的線性丟番圖方程和中國剩餘定理，也可以用來定義多項式的連分數展開式。多項式的輾轉相除法也有其他應用，如施圖姆定理，一個用於計算多項式在給定區間內的實根個數的方法。這被應用於其他領域，如控制論的勞斯-赫爾維茨穩定性判據。最後，多項式的係數不必侷限於整數、實數、甚至複數。這些係數可以是其他域中的元素，如上文所述的有限域formula_653。從輾轉相除法得出的結論也可以直接推廣至這類多項式。高斯整數.高斯整數是滿足formula_654的複數，其中formula_655和formula_656是普通整數，formula_657是虛數單位。透過在高斯整數中定義輾轉相除法，根據上文貝祖等式可以證明高斯整數的惟一分解。高斯整數的惟一分解性質在很多應用中都很重要，如計算勾股數或者證明費馬平方和定理。輾轉相除法用於這些應用很方便，但並非必不可少，一些定理也可以由其他方式證明。對於兩個高斯整數formula_658和formula_659的輾轉相除法和普通整數只有兩個區別。像整數一樣，演算法的第formula_660步計算出商formula_454和餘數formula_555：formula_564其中formula_664，formula_665，每個餘數都嚴格地小於前一個餘數，formula_666。第一個區別即是：商和餘數都是高斯整數，也就是複數，所以商"formula_454"是透過對實際比例的實部和虛部取最近似整數來找出的。第二個區別就是需要定義複數比較大小的方法。所以我們定義一個範數函式formula_670，以將高斯整數formula_671轉換成普通整數來比較大小。在每個步驟"formula_660"中，餘數的範數必須小於前一個餘數的範數formula_673。因為範數是非負整數並且在每一步都減小，所以輾轉相除法在有限步內一定能結束。最後一個非零餘數即是formula_658和formula_659的最大公約數，即能同時整除formula_658和formula_659的整數中範數最大的一個。若把乘以formula_678或formula_679的所得結果考慮在內，那麼可以說formula_658和formula_659的最大公約數是唯一的。很多其他應用如線性丟番圖方程、中國剩餘定理都適用於高斯整數，高斯整數的連分數也可以用輾轉相除法定義。歐幾里得整環.如果一個支援兩種二元運算的元素的集合形成一個交換環"R"並且可以使用輾轉相除法求最大公約數，那麼這個集合叫做歐幾里得整環。這兩個二元運算不必是平常算數中的加法和乘法，它們可以是更廣泛的概念，如群或么半群中的運算。但是這些運算仍然需要遵守交換律、結合律、分配律。推廣之後的輾轉相除法需要一個歐幾里得函式，即一個將formula_682對映到非負整數集合的函式formula_683，使得對於"formula_682"中非零元素formula_460和formula_461，"formula_682"中存在formula_567和formula_689滿足formula_690，formula_691。例如上文中用於高斯整數的範數函式。這個函式"formula_683"可以是數的絕對值或模，也可以是多項式的次數，只要輾轉相除法計算過程中它的值不斷減小就行，這樣演算法便能在有限步內結束。這非常依賴於非負整數的良序性，即每個非空的非負整數集合都有一個最小數。任何歐幾里得整環都滿足算數基本定理：歐幾里得整環中的數可以惟一分解。所以任何歐幾里得整環都是惟一分解整環，但反之不然。歐幾里得整環是GCD整環的子類。也就是說，在某些整環中，兩元素存在最大公約數但卻不能用輾轉相除法計算。歐幾里得整環都是主理想環，即其中每一個理想都是主理想，但並不是每個主理想環都是歐幾里得整環。歐幾里得整環的惟一分解性質在很多場合都非常有用。例如，高斯整數的惟一分解性質可以方便地匯出勾股數的公式，或者證明費馬平方和定理。惟一分解性質也是加百利·拉梅於1847年基於約瑟夫·劉維爾的建議發表的證明費馬最後定理的嘗試中的關鍵部分。拉梅的嘗試需要形如formula_693的數的惟一分解性質，其中formula_625和formula_695是整數，formula_696是1的formula_469次方根，即formula_698。雖然這對於某些"formula_469"成立，但在其他情況下並非總是正確的。惟一分解性質在分圓域的失效使恩斯特·庫默爾發明了理想數的概念，隨後理查德·戴德金創造了理想的概念。#重定向二次整數的惟一分解.二次整數環對於解釋歐幾里得整環很有幫助。二次整數是高斯整數的推廣，高斯整數中的虛數單位"i"被替換成一個複數ω。二次整數的形式是formula_701，其中formula_655和formula_656是整數，formula_704有兩種形式，取決於引數formula_705。如果"formula_705"不等於四的倍數加一，那麼：formula_707如果"formula_705"等於四的倍數加一，那麼：formula_709如果二次整數環有像上文用來比較高斯整數的那樣的範數函式，那麼它就是規範歐幾里德整環。只有當formula_710 −11, −7, −3, −2, −1, 2, 3, 5, 6, 7, 11, 13, 17, 19, 21, 29, 33, 37, 41, 57或73時，二次整數環才是規範歐幾里德整環。formula_710 −1和−3時的二次整數分別叫作高斯整數和艾森斯坦整數。但如果範數函式formula_683可以是任何歐幾里得函式，那麼使二次整數環是歐幾里得整環的"formula_705"的可能值到目前為止還不確定。是歐幾里得整環但不是規範歐幾里德整環的第一個例子發表於1994年。溫伯格於1973年證明，在廣義黎曼猜想成立的前提下，formula_715時的二次整數環是歐幾里得整環，當且僅當它是一個主理想環。非交換環.輾轉相除法也可以應用至非交換環，如赫爾維茨四元數。令formula_658和formula_659表示這樣一個環中的兩個元素。他們有右公約數formula_718如果formula_719, formula_720。因為乘法不符合交換律，也就有兩個版本的輾轉相除法，一個計算右公約數，一個計算左公約數。例如對於右公約數，輾轉相除法求最大公約數的第一步可以寫成：formula_728其中formula_729是商，formula_730是餘數。對於左公約數，第一步過程是：formula_731不管是哪一種，這個過程都會重複到最大左公約數或者最大右公約數計算出，像在歐幾里得整環中一樣，formula_730的“大小”一定小於formula_659，並且對於formula_730只有有限種的可能大小，這樣才能保證演算法能夠結束。由輾轉相除法得出的大多數結果都適用於非交換環。例如，貝祖等式表明最大右公約數可以表示成β的倍數的和，即，存在formula_735和formula_736使：formula_737對於最大左公約數，等式如下：formula_738貝祖等式可以用來解非交換環的丟番圖方程。推廣至其他數學結構.輾轉相除法有三個性質保證它不會永遠進行下去。第一，它可以寫成一系列遞迴式：formula_564其中每一個餘數都比前一個餘數小，formula_740。第二，餘數的大小有嚴格下限，如formula_741。第三，小於formula_742的數的數量是有限的。輾轉相除法推廣至其他數學結構，如和超限序數時仍保持這種性質。輾轉相除法的一個重要推廣是代數幾何中格羅布納基的概念。像前文所述，formula_460和formula_461的最大公約數formula_465是它們的理想的生成元素。也就是說，對任何整數formula_599和formula_600，存在另一個整數formula_468使：formula_749雖然這對一元多項式也成立，但是對多元多項式就不成立了。在多元多項式的情況下，生成元素的有限集合formula_750可以定義如下：formula_751其中"formula_599"、"formula_600"和formula_754是多元多項式。任何這樣的多元多項式formula_683可以表示成生成多項式的和加上惟一的餘數多項式formula_689, 通常叫做多項式"formula_683"的一般形式。formula_758雖然商多項式formula_454可能不惟一。這些生成多項式的集合就叫做格羅布納基。