查看“︁輾轉相除法”︁的源代码

{{NoteTA
|G1=Math
|G2=IT
|G3=PP
|1=zh-cn:数学对象;zh-tw:數學物件;
|2= zh-hans:余; zh-tw:餘;}}
[[File:Euclidean algorithm 252 105 animation flipped.gif|thumb|200px|辗转相除法的演示动画：<br>两条[[线段]]長分别可表示252和105，則其中每一小分段長代表最大公因數21。如动画所示，只要輾轉地从大数中减去小数，直到其中一段的长度为0，此时剩下的一条线段的长度就是252和105的最大公因数。]]

在[[數學]]中，'''辗转相除法'''，又称'''欧几里得算法'''（{{lang-en|Euclidean algorithm}}），是求[[最大公约数]]的[[算法]]。辗转相除法首次出现于[[欧几里得]]的《[[几何原本]]》（第VII卷，命题i和ii）中，而在[[中国]]则可以追溯至[[东汉]]出现的《[[九章算术]]》。

两个[[整数]]的最大[[公约数]]是能够同时[[整除]]它们的最大的正整数。辗转相除法基于如下原理：两个整数的最大公约数等于其中较小的数和两数相除余数的最大公约数。例如，欲求252和105的最大公约数（<math>252=21\times12;105=21\times5</math>）；因为<math>252\div105=2...42</math>，所以这个最大公约数也是42与105的最大公约数(<math>42=21\times2</math>)。在这个过程中，较大的数缩小了，所以继续进行同样的计算可以不断缩小这两个数直至余数为零。这时，所剩下的还没有变成零的数就是两数的最大公约数。由辗转相除法也可以推出，两数的最大公约数可以用两数的整数倍相加来表示，如<math>21=5\times 105+(-2) \times 252</math>。这个重要的結論叫做[[貝祖等式|貝祖定理]]。 

辗转相除法最早出现在欧几里得的《几何原本》中（大约[[公元前]]300年），所以它是现行的算法中歷史最悠久的。这个算法原先只用来处理[[自然数]]和几何长度（相當於正[[實數]]），但在19世纪，辗转相除法被推广至其他类型的[[數學物件]]，如[[高斯整数]]和一元[[多项式]]。由此，引申出[[欧几里得整环]]等等的一些现代[[抽象代数]]概念。后来，辗转相除法又扩展至其他数学领域，如[[纽结理论]]和[[多項式#定義|多元多项式]]。

辗转相除法有很多应用，它甚至可以用来生成全世界不同文化中的传统音乐节奏。<ref>[[Godfried Toussaint]], "The Euclidean algorithm generates traditional musical rhythms," ''Proceedings of BRIDGES: Mathematical Connections in Art, Music, and Science'', Banff, Alberta, Canada, July 31 to August 3, 2005, pp. 47–56.</ref>在现代[[密码学]]方面，它是[[RSA算法]]（一种在[[电子商务]]中广泛使用的[[公钥加密]]算法）的重要部分。它还被用来解[[丢番图方程]]，比如寻找满足[[中国剩余定理]]的数，或者求[[有限域]]中[[元素 (數學)|元素]]的[[逆元素|逆]]。辗转相除法还可以用来构造[[连分数]]，在[[施图姆定理]]和一些[[整数分解]]算法中也有应用。辗转相除法是现代[[数论]]中的基本工具。

辗转相除法处理大数时非常高效，如果用除法而不是减法实现，它需要的步骤不会超过较小数的位数（[[十进制]]下）的五倍。[[拉梅]]于1844年证明了这点，同時這也標誌著[[计算复杂性理论]]的開端。

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

如果<math>\gcd(a,b)=1</math>，則稱<math>a</math>和<math>b</math>[[互素]]。<ref>Stark, p. 21.</ref>''a''和''b''是否互素和它们是否[[素数]]无关。<ref>LeVeque, p. 32.</ref>如，6和35都不是素数，因为它们都可以分解为多于一个素因数的乘积：6 = 2 × 3，35 = 5 × 7。但是，6和35互素，因为除了1以外没有自然数同时整除6和35。

[[File:Square tiling 24x60.svg|thumb|150px|一个24×60的长方形正好被十个12×12的方格填满，其中12是24和60的最大公约数。一般地，当且仅当<math> c </math>是<math> a </math>和<math> b </math>的公约数时，<math> a\times b </math>尺寸的长方形可被边长''c''的正方形正好填满。]]

令<math>g=\gcd(a, b)</math>。由于<math>a</math>和<math>b</math>都是''<math>g</math>''的整数倍，所以可以写成<math>a = mg,b = ng</math>，并且不存在更大的整数<math>G>g</math>使等式成立。为了使''<math>g</math>''尽可能大，就要使<math>a</math>和<math>b</math>中所有公约数都提取出来归入''<math>g</math>''中，所以自然数<math>m</math>和<math>n</math>一定互素，并且<math>a</math>和<math>b</math>的最大公约数''<math>g</math>''可以被<math>a</math>和<math>b</math>的所有其他公因数<math>c</math>整除。<ref>Leveque, p. 31.</ref>

我们可以用右图来解释最大公约数的概念：<ref>{{cite book | author = Grossman JW | year = 1990 | title = Discrete Mathematics | publisher = Macmillan | location = New York | isbn = 0-02-348331-8 | page = 213}}</ref>設一个长方形的边长为<math>a</math>和<math>b</math>。因为<math>a</math>和<math>b</math>的任何公约数''<math>c</math>''都可以整除<math>a</math>和<math>b</math>，所以长方形的边都可以等分为长度为''<math>c</math>''的线段，也就是长方形可以被边长为''<math>c</math>''的正方形正好填满。而最大公约数''<math>g</math>''是所有可能的''<math>c</math>''中最大的一个。例如，一个24 × 60的长方形区域可以分成1 × 1、2 × 2、3 × 3、6 × 6或12 × 12的正方形网格。也就是说，12是24和60的最大公约数。

<math>a</math>和<math>b</math>的最大公约数是两数共有的素因数的乘积。<ref name="Schroeder_21" >Schroeder, pp. 21–22.</ref>例如，462可以分解成2&nbsp;×&nbsp;3&nbsp;×&nbsp;7&nbsp;×&nbsp;11；1071可以分解成3&nbsp;×&nbsp;3&nbsp;×&nbsp;7&nbsp;×&nbsp;17。462和1071的最大公约数等于它们共有的素因数的乘积3&nbsp;×&nbsp;7&nbsp;=&nbsp;21。如果两数没有公共的素因数，那么它们的最大公约数是1，也即这两个数互素。辗转相除法的优点就在於它能以有系統的方式求出兩數的最大公约数，而無需分別對它們作因式分解。<ref>Schroeder, p. 19.</ref><ref>{{cite book | author = Ogilvy CS, Anderson JT | year = 1966 | title = Excursions in number theory | publisher = [[牛津大學出版社|Oxford University Press]] | location = New York | id = {{LCCN|66|0|14484}} | pages = 27–29}}</ref>大数的[[素因数分解]]被認為是一個困難的問題，即使是现代的计算机也非常难於處理，所以许多加密系统的原理都是建基於此。<ref name="Schroeder_216" >Schroeder, pp. 216–219.</ref>

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

三个数的最大公约数的定义和两个数的相同，即是它们共有的素因数的积<ref>Stark, p. 25.</ref>，它们或者也可以按下式计算<ref>Ore, pp. 47–48.</ref>：

: <math>\gcd(a, b, c) = \gcd(a, \gcd(b, c)) = \gcd(\gcd(a, b), c) = \gcd(\gcd(a, c), b).</math>

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

=== 归纳、递归和无穷递降 ===
下文的論證會用到三種相關的数学方法，分別是[[数学归纳法]]、[[递归]]和[[无穷递降]]。数学归纳法<ref>{{cite book|author=高德纳|year=1997|title=The Art of Computer Programming（[[计算机程序设计艺术]]）, Volume 1: Fundamental Algorithms|edition=3rd|publisher=Addison-Wesley|isbn=0-201-89683-4}} (Section 1.2.1: Mathematical Induction, pp. 11–21.)</ref>经常用来证明某個定理對所有[[自然数]]成立：<ref>Rosen, pp. 18–21.</ref>首先证明定理对一个特定的数<math>n_0</math>成立（通常是1）；然后證明如果定理对自然数<math>n</math>成立的話，那麼它对自然数<math>n+1</math>成立。這樣，便可證明定理对所有大于<math>n_0</math>的自然数也成立。递归<ref>Rosen, pp. 21–24.</ref>是将相关的数组成一个[[数列]]（<math>a_1,a_2,a_3,\cdots</math>），<ref>{{cite book | author = Anderson JA | year = 2001 | title = Discrete Mathematics with Combinatorics | url = https://archive.org/details/discretemathemat0000ande | publisher = Prentice Hall | location = Upper Saddle River, NJ | isbn = 0-13-086998-8 | pages = [https://archive.org/details/discretemathemat0000ande/page/165 165]–223}}</ref>當中除初始項外，其中每一项都用前一项或前几项表示。如[[斐波那契数列]]就是递归的，每一项<math>F_n</math>都等于<math>F_{n-1}+F_{n-2}</math>（<math>n\geqq 2</math>）。辗转相除法中的一些等式也是递归的。最后，无穷递降<ref>Rosen, p. 492.</ref>是用方程的一个自然数解导出比它小的自然数解。<ref>{{cite book | author = Anderson JA | year = 2001 | title = Discrete Mathematics with Combinatorics | url = https://archive.org/details/discretemathemat0000ande | publisher = Prentice Hall | location = Upper Saddle River, NJ | isbn = 0-13-086998-8 | pages = [https://archive.org/details/discretemathemat0000ande/page/109 109]–119}}</ref>但是，这种转化不能永远进行下去，因为只有有限個小於原來的自然数解的自然数。所以，要麼方程無解，不然在有限步内必然能得出最小的自然數解。在下文會用到此法來证明辗转相除法一定会在有限步内结束。

== 算法描述 ==
=== 计算过程 ===
辗转相除法是一种[[递归]]算法，每一步计算的输出值就是下一步计算时的输入值。<ref name=autogenerated3>Stark, pp. 16–20.</ref>设<math>k</math>表示步骤数（从0开始计数），算法的计算过程如下。

每一步的输入是都是前两次计算的非負余数<math>r_{k-1}</math>和<math>r_{k-2}</math>。因为每一步计算出的余数都在不断减小，所以，<math>r_{k-1}</math>小于<math>r_{k-2}</math>。在第''<math>k</math>''步中，算法计算出满足以下等式的[[商數|商]]<math>q_k</math>和[[余数]]<math>r_k</math>：

:<math>r_{k-2}=q_k r_{k-1}+r_k</math>

其中<math>0\leq r_k<r_{k-1}</math>。也就是<math>r_{k-2}</math>要不断减去<math>r_{k-1}</math>直到比<math>r_{k-1}</math>小。

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

:<math>a=q_0 b+r_0</math>
:<math>b=q_1 r_0+r_1</math>
:<math>r_0=q_2 r_1+r_2</math>
:<math>r_1=q_3 r_2+r_3</math>
:<math>...</math>

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

由于每一步的余数都在减小并且不为负数，必然存在第<math>n</math>步时<math>r_n</math>等于0，使算法终止<ref name="Stark_p18" >Stark, p. 18.</ref>，<math>r_{n-1}</math>就是''<math>a</math>''和''<math>b</math>''的最大公约数。其中''<math>n</math>''不可能无穷大，因为在<math>r_0</math>和0之间只有有限个自然数。

=== 正确性的证明 ===
辗转相除法的正确性可以分成两步来证明。<ref name=autogenerated3 />在第一步，我們會證明算法的最终结果<math>r_{n-1}</math>同时整除''<math>a</math>''和''<math>b</math>''。因为它是一个公约数，所以必然小于或者等于最大公约数<math>g</math>。在第二步，我們證明''<math>g</math>''能整除<math>r_{n-1}</math>。所以''<math>g</math>''一定小于或等于<math>r_{n-1}</math>。两个不等式只在<math>r_{n-1}=g</math>时同时成立。

具体证明如下：

#證明<math>r_{n-1}</math>同時整除''<math>a</math>''和''<math>b</math>''：
#:因爲餘數<math>r_n</math>是0，<math>r_{n-1}</math>能夠整除<math>r_{n-2}</math>：
#::<math>r_{n-2}=q_n r_{n-1}+r_{n}</math> 
#:因爲<math>r_{n-1}</math>能夠整除<math>r_{n-2}</math>，所以也能夠整除<math>r_{n-3}</math>：
#::<math>r_{n-3}=q_{n-1}r_{n-2}+r_{n-1}</math>
#:同理可證<math>r_{n-1}</math>可以整除所有之前步驟的餘數，包括''<math>a</math>''和''<math>b</math>''，即<math>r_{n-1}</math>是''<math>a</math>''和''<math>b</math>''的公約數，<math>r_{n-1}\leq g</math>。
#證明最大公約數<math>g</math>能整除<math>r_{n-1}</math>：
#:根據定義，''<math>a</math>''和''<math>b</math>''可以寫成<math>g</math>的倍數：<math>a=mg</math>、<math>b=ng</math>，其中<math>m</math>和<math>n</math>是自然數。
#:因爲<math>r_0=a-q_0 b=mg-q_0 ng=(m-q_0 n)g</math>，所以<math>g</math>整除<math>r_0</math>。 同理可證<math>g</math>整除每個餘數<math>r_1,r_2,\ldots, r_{n-1}</math>。
#:因爲最大公約數<math>g</math>整除<math>r_{n-1}</math>，因而<math>g\leq r_{n-1}</math>。
#所以<math>g= r_{n-1}</math>。即：<ref>高德纳, p. 320.</ref><ref name="Lovasz_2003">{{cite book | author = Lovász L, Pelikán J, Vesztergombi K | year = 2003 | title = Discrete Mathematics: Elementary and Beyond | publisher = Springer-Verlag | location = New York | isbn = 0-387-95584-4 | pages = 100–101}}</ref>
#:<math>g=\gcd(a, b)=\gcd(b, r_0)=\gcd(r_0, r_1)=\ldots=\gcd(r_{n-2}, r_{n-1})=r_{n-1}</math>

=== 举例 ===
[[File:Euclidean algorithm 1071 462.gif|right|thumb|220px|算法的演示动画。最初的绿色矩形的长和宽分别是<math>a=1071</math>、<math>b=462</math>，从中不断铺上462×462的正方形直到剩下部分面积是462×147；然后再铺上147×147的正方形直至剩下21×147的面积；最后，铺上21×21的正方形时，绿色部分就没有了。即21是1071和462的最大公约数。]]

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

: <math>1071 = 2 \times 462 + 147.</math>

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

: <math>462 = 3 \times 147 + 21.</math>

再从147中不断减去21直到小于21（可以减7次，即<math>q_2=7</math>），没有余数：

: <math>147 = 7 \times 21 + 0.</math>

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

{| class="wikitable"
|-
! 步骤数 !! 算式 !!商和余数
|-
| 0 || <math>1071 = 462 q_0 + r_0</math>|| <math>q_0=2</math>、<math>r_0=147</math>
|-
| 1 || <math>462 = 147 q_1 + r_1</math>|| <math>q_1 = 3</math>、<math>r_1 = 21</math>
|-
| 2 || <math>147 = 21 q_2 + r_2</math>|| <math>q_2 = 7</math>、<math>r_2 = 0</math>（算法终止）
|}

=== 图形演示 ===
辗转相除法的计算过程可以用图形演示。<ref name="Kimberling_1983">{{cite journal | author = Kimberling C | year = 1983 | title = A Visual Euclidean Algorithm | url = https://archive.org/details/sim_mathematics-teacher_1983-02_76_2/page/108 | journal = Mathematics Teacher | volume = 76 | pages = 108–109}}</ref>假设我们要在<math>a\times b</math>的[[矩形]]地面上铺[[正方形]]瓷砖，并且正好铺满，其中<math>a</math>大于<math>b</math>。我们先尝试用<math>b\times b</math>的瓷砖，但是留下了<math>r_0\times b</math>的部分，其中<math>r_0<b</math>。我们接着尝试用<math>r_0\times r_0</math>的正方形瓷砖铺，又留下了<math>r_1\times r_0</math>的部分，然后再使用<math>r_1\times r_1</math>的正方形铺……直到全部铺满为止，即到某步时正方形刚好覆盖剩余的面积为止。此时用到的最小的正方形的边长就是原来矩形的两条边长的最大公约数。在图中，最小的正方形面积是21×21（{{color|red|红色}}），而原先的矩形（{{color|green|绿色}}）边长是1071×462，所以21是1071和462的最大公约数。

=== 计算商和余数 ===
{{See also|模除|带余除法}}

在每个步骤<math>k</math>中，辗转相除法都需要计算两个数<math>r_{k-1}</math>和<math>r_{k-2}</math>的商<math>q_k</math>和余数<math>r_k</math>：

: <math>r_{k-2}=q_k r_{k-1}+r_k</math>

其中<math>0\leq r_k < r_{k-1}</math>。除法的算法保证这样的商和余数总是存在。自然数的除法算法还指出这样的商和余数是惟一的，但这对辗转相除法而言并非必要。<ref name="Cohn_1962">Cohn, pp. 104–110.</ref>

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

:<math>r_k \equiv r_{k-2} \bmod r_{k-1}</math>

=== 计算机实现 ===
辗转相除法可用[[伪代码]]表示，比如除法版本可以寫成<ref>高德纳, pp. 319–320.</ref>

 '''function''' gcd(a, b)
     '''while''' b ≠ 0
         t ← b
         b ← a '''mod''' b
         a ← t
     '''return''' a
C++版本：<syntaxhighlight lang="c++" line="1">
int gcd(int m, int n) {
    int t = 1;
    while(t != 0) {
        t = m % n;
        m = n;
        n = t;
    }
    return m;
}
</syntaxhighlight>
Rust版本：<syntaxhighlight lang="rust" line="1">
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()) 
        },
    }
}
</syntaxhighlight>
Python 3版本：<syntaxhighlight lang="python3" line="1">
def gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a
</syntaxhighlight>
在第<math>k</math>次循环开始时，变量<math>b</math>的值是前一次运算的余数<math>r_{k-1}</math>，变量<math>a</math>的值是再前一次运算的余数<math>r_{k-2}</math>。步骤<math>b:=a \bmod b</math>的作用等同于递归式<math>r_k \equiv r_{k-2} \bmod r_{k-1}</math>。变量<math>t</math>的功能是在下一个余数<math>r_k</math>计算过程中临时性地保存<math>r_{k-1}</math>的值。在一次循环结束时，变量''<math>b</math>''的值是前一次运算的余数''<math>r_k</math>''，变量''<math>a</math>''的值是再前一次运算的余数<math>r_{k-1}</math>。

在欧几里得定义的减法版本，取餘运算被减法替换。<ref>高德纳, pp. 318–319.</ref>

 '''function''' gcd(a, b)
     '''if''' a = 0
        '''return''' b
     '''while''' b ≠ 0
         '''if''' a > b
            a ← a − b
         '''else'''
            b ← b − a
     '''return''' a

变量''<math>a</math>''和''<math>b</math>''的值分别是前两次的余数<math>r_{k-1}</math>和<math>r_{k-2}</math>。假定第''<math>k</math>''次循环开始时''<math>a</math>''大于''<math>b</math>''，那么''<math>a</math>''等于<math>r_{k-2}</math>，因为<math>r_{k-2} > r_{k-1}</math>。在循环过程中，''<math>a</math>''重复减去''<math>b</math>''直到比''<math>b</math>''小，此时''<math>a</math>''就是下一个余数''<math>r_k</math>''；然后''<math>b</math>''重复减去''<math>a</math>''直到比''<math>a</math>''小，此时''<math>b</math>''就是下一个余数<math>r_{k+1}</math>；重复执行直到<math>b=0</math>。

以下是[[递归]]版本<ref>Stillwell, p. 14.</ref>：

 '''function''' gcd(a, b)
     '''if''' b = 0
        '''return''' a
     '''else'''
        '''return''' gcd(b, a '''mod''' b)
C++[[递归]]版本如下：<syntaxhighlight lang="c++" line="1">
int gcd(int n,int m)
{
    return  m == 0 ? n : gcd(m, n % m);
}
</syntaxhighlight>

Rust递归版本：<syntaxhighlight lang="rust" line="1">
fn gcd(x: isize, y: isize) -> Option<isize> {
    match (x,y) {
        (0, 0)  => None,
        (a, 0)  => Some(a.abs()),
        _       => gcd(y, x % y),
    }
}
</syntaxhighlight>

Java版本：<syntaxhighlight lang="java" line="1">
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 );
        }
    }
}
</syntaxhighlight>
Python 3版本：<syntaxhighlight lang="python3" line="1">
def gcd(a, b):
    return a if b == 0 else gcd(b, a % b)
</syntaxhighlight>例如<math>\gcd(1071,462)</math>的计算过程是：函数的第一次调用计算<math>\gcd(462,1071 \bmod 462)= \gcd(462,147)</math>；下一次调用计算<math>\gcd(147,462 \bmod 147)=\gcd(147,21)</math>，在接下来是<math>\gcd(21,147\bmod 21)=\gcd(21,0)=21</math>。

=== 使用绝对值最小的余数 ===
在另一个版本的算法中，每一步还要把取余运算时计算出的商增加一后再重新计算余数（此时计算出的余数应该是负的），然后取两个余数的绝对值较小的数作为下一步运算时使用的余数。<ref name="Ore_least_abs_remainders" >Ore, p. 43.</ref><ref name="Stewart_1964">{{cite book | author = Stewart BM | year = 1964 | title = Theory of Numbers | edition = 2nd | publisher = Macmillan | location = New York | id = {{LCCN|64|0|10964}} | pages = 43–44}}</ref>取余运算后，设''<math>r_k</math>''是计算出的余数（此時為正），<math>q</math>是计算出的商：

: <math>r_{k-2}=q_k r_{k-1}+r_k</math>

即假設<math>r_{k-1}>r_k>0</math>。然後使用以下式子计算出一个负的余数<math>e_k</math>：

: <math>r_{k-2}=(q_k +1)r_{k-1}+e_k</math>

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

== 历史发展 ==
[[File:Euklid.jpg|thumb|辗转相除法可能在[[欧几里得]]之前几个世纪就已经有了。图为使用两脚规进行测量。]]

辗转相除法是目前仍然在使用的历史最悠久的算法之一。<ref name=autogenerated2>高德纳, p. 318.</ref>它首次出现于《[[几何原本]]》（卷7命题1–2、卷10命题2–3）（大约公元前300年）。在卷7中用于整数，在卷10中用于线段的长度（以現代的觀點看，线段的长度可視為正实数，也就是說辗转相除法實際可用於實數上，但是当时未有实数的概念）。卷10中出现的算法是几何的，两段线段''a''和''b''的最大公约数是''a''和''b''的[[通約性|公度]]中的最大值。

这个算法可能并非[[欧几里得]]发明，因為他也有将先前其他數學家的一些成果编进他的《几何原本》。<ref name="Weil_1983">{{cite book | author = [[André Weil|Weil A]] | year = 1983 | title = Number Theory | publisher = Birkhäuser | location = Boston | isbn = 0-8176-3141-0 | pages = 4–6}}</ref><ref name="Jones_1994">{{cite book | author = Jones A | year = 1994 | chapter = Greek mathematics to AD 300 | title = Companion encyclopedia of the history and philosophy of the mathematical sciences | publisher = Routledge | location = New York | isbn = 0-415-09238-8 | pages = 46–48}}</ref>数学家、历史学家[[范德瓦尔登]]认为卷7的内容可能来自[[毕达哥拉斯]]学院出身的数学家写的关于[[数论]]的教科书。<ref name="van_der_Waerden_1954">{{cite book | author = [[Bartel Leendert van der Waerden|van der Waerden BL]] | year = 1954 | title = Science Awakening | url = https://archive.org/details/scienceawakening00waer| series = translated by Arnold Dresden | publisher = P. Noordhoff Ltd | location = Groningen | pages = [https://archive.org/details/scienceawakening00waer/page/114 114]–115}}</ref>辗转相除法在當時很可能已為[[尤得塞斯]]（大約公元前375年）所知
<ref name=autogenerated2 /><ref>{{cite journal | author = von Fritz K | date = 1945 | title = The Discovery of Incommensurability by Hippasus of Metapontum | url = https://archive.org/details/sim_annals-of-mathematics_1945-04_46_2/page/242 | journal = Ann. Math. | volume = 46 | pages = 242–264 | doi = 10.2307/1969021}}</ref>，甚至可能更早之前就已经存在<ref>{{cite book | author = [[T. L. Heath|Heath TL]] | year = 1949 | title = Mathematics in Aristotle | url = https://archive.org/details/mathematicsarist00heat| publisher = Oxford Press | pages = [https://archive.org/details/mathematicsarist00heat/page/n92 80]–83}}</ref><ref>{{cite book | author = [[David Fowler (mathematician)|Fowler DH]] | year = 1987 | title = The Mathematics of Plato's Academy: A New Reconstruction | url = https://archive.org/details/mathematicsofpla0000fowl_h9l3 | publisher = Oxford University Press | location = Oxford | isbn = 0-19-853912-6 | pages = [https://archive.org/details/mathematicsofpla0000fowl_h9l3/page/31 31]–66}}</ref>，因为欧几里得和[[亚里士多德]]的著作中都出现了{{lang|el|ἀνθυφαίρεσις}}一词（意为“辗转相减”）。<ref>{{cite journal | author = Becker O | year = 1933 | title = Eudoxus-Studien I. Eine voreuklidische Proportionslehre und ihre Spuren bei Aristoteles und Euklid | journal = Quellen und Studien zur Geschichte der Mathematik B | volume = 2 | pages = 311–333}}</ref>

几个世纪之后，辗转相除法又分别被[[中国]]人和[[印度]]人独立发现，<ref name=autogenerated4>Stillwell, p. 31.</ref>主要用来解天文学中用到的[[丢番图方程]]以及制定准确的历法。5世纪末，印度[[数学家]]、[[天文学家]][[阿里亚哈塔]]曾稱辗转相除法为“粉碎机”，這可能是因为它在解[[丢番图方程]]时很有效<ref>Rosen, pp. 86–87.</ref>。<ref name="#1">Tattersall, p. 70.</ref>在中国，《[[九章算术]]》中提到了一种类似辗转相减法的“更相减损术”<ref>{{cite wikisource |title=九章算术 |plainchapter=卷第一　方田以御田疇界域| wslink=九章算術#-.7BA.7Czh-hans:.E5.8D.B7.3Bzh-hant:.E5.8D.B7.7D-.E7.AC.AC.E4.B8.80.E3.80.80.E6.96.B9.E7.94.B0.E4.BB.A5.E5.BE.A1.E7.94.B0.E7.96.87.E7.95.8C.E5.9F.9F| quote=可半者半之；不可半者，副置分母、子之數，以少減多，更相減損，求其等也。以等數約之。|wslanguage=zh}}</ref>。《[[孙子算经]]》中則出现了[[中国剩余定理]]的一个特例<ref>Ore, pp. 247–248.</ref>，但是直到1247年[[秦九韶]]才於其《[[数学九章]]》中解答了該定理的一般情況，當中用到了他發明的[[大衍求一术]]。此法的其中一部分實際上便是輾轉相除的原理，秦九韶在書中對此有明確表述。<ref>{{cite web|author1=洪萬生|title=中國π的一頁滄桑|url=http://episte.math.ntu.edu.tw/articles/sm/sm_08_05_3/page5.html|accessdate=2015-04-28|archive-date=2016-03-05|archive-url=https://web.archive.org/web/20160305021005/http://episte.math.ntu.edu.tw/articles/sm/sm_08_05_3/page5.html}}</ref>在欧洲，辗转相除法首次出现于{{link-en|克劳德·巴希特|Claude Gaspard Bachet de Méziriac}}的著作《愉悦讨喜的问题》（''{{lang|fr|Problèmes plaisants et délectables}}''）的第二版<ref name="#1"/>在欧洲，辗转相除法被用于丢番图方程和構建[[连分数]]。后来，英国数学家{{link-en|桑德森|Nicholas Saunderson}}在其著作中收編了[[扩展欧几里得算法]]，作为一個有效计算连分数的方法。他將此法的來源歸名於{{link-en|罗杰·科茨|Roger Cotes}}。<ref>Tattersall, pp. 72–76.</ref>

19世纪，辗转相除法促成了新[[数系]]的建立，如[[高斯整数]]和[[艾森斯坦整数]]。1815年，[[高斯]]用辗转相除法证明高斯整数的分解是惟一的，儘管他的研究到了1832年才首度发表。<ref name="Gauss_1832" />高斯在他的《[[算数研究]]》（出版于1801年）中實際上也有援引这个算法，但僅是以[[连分数]]方法的形式敘述。<ref name=autogenerated4 />[[约翰·彼得·古斯塔夫·勒热纳·狄利克雷|约翰·狄利克雷]]是第一个将辗转相除法作为数论的基础的数学家。{{fact}}狄利克雷提出，数论中的很多结论，如分解的惟一性，在任何使辗转相除法適用的数系中均有效。<ref>狄利克雷, pp. 29–31.</ref>狄利克雷的數論講義後來經[[理查德·戴德金]]編輯和推广，戴德金也有以辗转相除法來研究[[代数整数]]。比如，他是第一个用高斯整数的分解惟一性证明[[费马平方和定理]]的数学家。<ref>{{cite book | author = [[理查德·戴德金|Dedekind R]] | year = 1894 | chapter = Supplement XI | title = Vorlesungen über Zahlentheorie | editor = PGL 狄利克雷 }}</ref>戴德金还率先定义了[[欧几里得整环]]的概念。19世纪末，戴德金所定義的[[理想 (环论)|理想]]概念使得數論的重心不必建基於輾轉相除法，從而促進了理論的發展。<ref>{{cite book | author = [[John Stillwell|Stillwell J]] | year = 2003 | title = Elements of Number Theory | publisher = Springer-Verlag | location = New York | isbn = 0-387-95587-9 | pages = 41–42}}</ref>
{| class="toccolours" style="float: left; margin-left: 1em; margin-right: 1em; font-size: 85%; background:#c6dbf7; color:black; width:23em; max-width: 25%;" cellspacing="5"
| style="text-align: left;" |
“欧几里得算法是所有算法的鼻祖，因为它是现存最古老的非凡算法。”
|-
| style="text-align: left;" | ——[[高德纳]]，《[[计算机程序设计艺术]]，第二卷：半数值算法》，第二版 (1981), p. 318.
|}
辗转相除法的其他应用发展于19世纪。1829年，[[雅克·夏尔·弗朗索瓦·施图姆|施图姆]]将辗转相除法用于[[施图姆定理|施图姆序列]]（用于确定多项式的不同实根的个数的方法）。<ref>{{cite journal | author = Sturm C | year = 1829 | title = Mémoire sur la résolution des équations numériques | journal = Bull. des sciences de Férussac | volume = 11 | pages = 419–422}}</ref>

辗转相除法是历史上第一个{{link-en|整数关系算法|integer relation algorithm}}，即寻找两個[[通約性|可通約]]實數的整数关系的算法。近年来，出现了一些新颖的整数关系算法，如{{link-en|埃拉曼·弗格森|Helaman Ferguson}}和福尔卡德于1979年发表的[[弗格森-福尔卡德算法]]（Ferguson–Forcade algorithm）
<ref>{{cite mathworld|urlname=IntegerRelation|title=Integer Relation|Ferguson–Forcade algorithm}}</ref>、以及与它相关的{{link-en|LLL算法|Lenstra–Lenstra–Lovász lattice basis reduction algorithm}}、[[HJLS算法]]以及[[PSLQ算法]]。<ref>{{cite journal | author = Peterson I | date = 12 August 2002 | title = [http://www.sciencenews.org/view/generic/id/172/title/Math_Trek__Jazzing_Up_Euclids_Algorithm Jazzing Up Euclid's Algorithm] | journal = ScienceNews }}</ref><ref>{{cite journal | author = Cipra BA | title = [http://amath.colorado.edu/resources/archive/topten.pdf The Best of the 20th Century: Editors Name Top 10 Algorithms] | journal = SIAM News | volume = 33 | number = 4 | date = 16 May 2000 | publisher = [[Society for Industrial and Applied Mathematics]]}}</ref>

1969年，科尔（Cole）和戴维（Davie）基于辗转相除法创造了一种二人游戏，叫做「欧几里得游戏」。<ref>{{cite journal | author = Cole AJ, Davie AJT | year = 1969 | title = A game based on the Euclidean algorithm and a winning strategy for it | url = https://archive.org/details/sim_mathematical-gazette_1969-12_53_386/page/354 | journal = Math. Gaz. | volume = 53 | pages = 354–357 | doi = 10.2307/3612461}}</ref>这个游戏有最优策略。<ref>{{cite journal | author = Spitznagel EL | year = 1973 | title = Properties of a game based on Euclid's algorithm | journal = Math. Mag. | volume = 46 | pages = 87–92}}</ref>游戏开始于两列分别为''a''和''b''个棋子组成的序列，玩家轮流从较长一列中取走较短一列棋子数量的''m''倍的棋子。如果两列棋子''p''和''q''分别由''x''和''y''个棋子组成，其中''x''大于''y''，那么玩家可以將序列''p''的棋子数量减少为自然数''x'' − ''my''。最后率先将一列棋子清空的玩家胜出。<ref>Rosen, p. 95.</ref><ref>{{cite book | author = Roberts J | year = 1977 | title = Elementary Number Theory: A Problem Oriented Approach | url = https://archive.org/details/Elementary_00_Robe | publisher = [[MIT Press]] | location = Cambridge, MA | isbn = 0-262-68028-9 | pages = [https://archive.org/details/Elementary_00_Robe/page/1 1]–8}}</ref>

== 数学上的应用 ==
=== 贝祖等式 ===
[[贝祖等式]]说明，两个数<math>a</math>和<math>b</math>的最大公约数<math>g</math>可以表示为<math>a</math>和<math>b</math>的线性和。<ref>{{cite book | author = Jones GA, Jones JM | year = 1998 | chapter = Bezout's Identity | title = Elementary Number Theory | publisher = Springer-Verlag | location = New York | pages = 7–11}}</ref>也就是说，存在整数<math>s</math>和<math>t</math>使<math>g=sa+tb</math>。<ref>Rosen, p. 81.</ref><ref>Cohn, p. 104.</ref>

整数<math>s</math>和<math>t</math>可以从辗转相除法算出的商<math>q_0,q_1,\cdots</math>计算出。<ref>Rosen, p. 91.</ref> 从辗转相除法的最后一步开始，''<math>g</math>''可以表示成前一步的商<math>q_{N-1}</math>和前两步的余数<math>r_{N-2}</math>和<math>r_{N-3}</math>：

: <math>g=r_{N-1}=r_{N-3}-q_{N-1}r_{N-2}</math>

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

: <math>r_{N-2}=r_{N-4}-q_{N-2}r_{N-3}</math>
: <math>r_{N-3}=r_{N-5}-q_{N-3}r_{N-4}</math>

将这两行式子先後代入第一个式子，可以将<math>g</math>表示成<math>r_{N-4}</math>和<math>r_{N-5}</math>的线性和。重复进行迭代直到出现<math>a</math>和<math>b</math>：
: <math>r_2=r_0-q_2 r_1</math>
: <math>r_1=b-q_1 r_0</math>
: <math>r_0=a-q_0 b</math>
最终，''g''可以表示成<math>a</math>和<math>b</math>的线性和：<math>g=sa+tb</math>。[[贝祖等式]]以及以上证明都可以扩展至[[欧几里得整环]]。

=== 主理想和相关问题 ===
贝祖等式提供了另一种定义<math>a</math>和<math>b</math>的最大公约数''<math>g</math>''的方法。<ref name="Leveque_p33" >Leveque, p. 33.</ref>考虑形如<math>ua+vb</math>（其中<math>u</math>和<math>v</math>是整数）的数的[[集合 (数学)|集合]]。因为<math>a</math>和<math>b</math>都可以被''<math>g</math>''整除，所以这个集合中的所有元素都可以被''<math>g</math>''整除。也就是说这个集合中的数都可以表示成''<math>g</math>''的倍数，或者<math>a</math>和<math>b</math>的其他公约数的倍数。但是，只有最大公约数才是这个集合的元素。根据贝祖等式，有<math>g=sa+tb</math>。換言之，当<math>u=s</math>、<math>v=t</math>时得出''<math>g</math>''。任何其他的公约数都不是这个集合的元素，因为它们都不能被比它们大的''<math>g</math>''整除。相反地，''<math>g</math>''的任何倍数都属于这个集合，只要令<math>u=ms</math>、<math>v=mt</math>，便有：

: <math>mg=msa+mtb</math>

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

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

=== 扩展欧几里得算法 ===
{{main|扩展欧几里得算法}}
[[贝祖等式]]的整数''s''和''t''可以通过[[扩展欧几里得算法]]算出。这个扩展算法在原有辗转相除法的基础上增加了两个递归等式：<ref>Rosen, pp. 90–93.</ref>
:<math>s_k=s_{k-2}-q_k s_{k-1}</math>
:<math>t_k=t_{k-2}-q_k t_{k-1}</math>

算法开始时：
:<math>s_{-2}=1</math>, <math>t_{-2}=0</math>
:<math>s_{-1}=0</math>, <math>t_{-1}=1</math>
加上这兩个递归式后，当算法终止于<math>r_N=0</math>，贝祖等式的整数<math>s</math>和<math>t</math>分别由<math>s_N</math>和<math>t_N</math>给出。

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

: <math>r_j=s_j a+t_j b</math>

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

: <math>r_k=r_{k-2}-q_k r_{k-1}</math>

因为<math>r_{k-2}</math>和<math>r_{k-1}</math>被假定是正确的，所以可以用<math>s</math>和<math>t</math>表示：

: <math>r_k=(s_{k-2} a+t_{k-2} b)-q_k(s_{k-1} a+t_{k-1} b)</math>

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

: <math>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</math>

=== 矩阵法 ===

整数<math>s</math>和<math>t</math>也可以用[[矩阵]]运算得出。<ref name="Koshy_2002">{{cite book | author = Koshy T | year = 2002 | title = Elementary Number Theory with Applications | publisher = Harcourt/Academic Press | location = Burlington, MA | isbn = 0-12-421171-2 | pages = 167–169}}</ref>辗转相除法的计算过程：
: <math>a=q_0 b+r_0</math>
: <math>b=q_1 r_0 +r_1</math>
: ...
: <math>r_{N-2}=q_N r_{N-1}+0</math>
可以写作2×2的商矩阵乘以一个2维余数向量：

:<math>
\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}
</math>

令<math>\mathbf{M}</math>表示所有商矩阵的乘积：

:<math>
\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}
</math>

这使辗转相除法化简为：

:<math>
\begin{pmatrix} a \\ b \end{pmatrix} =
\mathbf{M} \begin{pmatrix} r_{N-1} \\ 0 \end{pmatrix} =
\mathbf{M} \begin{pmatrix} g \\ 0 \end{pmatrix}
</math>

如要用<math>a</math>和<math>b</math>的线性和表示<math>g</math>，可將等式两边同时乘以矩阵'''<math>\mathbf{M}</math>'''的[[逆矩阵]]。<ref name="Koshy_2002" /><ref name="Bach_1996">{{cite book | author = Bach E, Shallit J | year = 1996 | title = Algorithmic number theory | publisher = MIT Press | location = Cambridge, MA | isbn = 0-262-02405-5 | pages = 70–73}}</ref>'''<math>\mathbf{M}</math>'''的[[行列式]]等于<math>(-1)^{N+1}</math>，因为它等于商矩阵的行列式的乘积，而每一个的行列式都是−1。因为'''<math>\mathbf{M}</math>'''的行列式不为零，最终的余数向量可以利用'''<math>\mathbf{M}</math>'''的逆矩阵解出：

:<math>
\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}
</math>

由上式可以得出<math>g=(-1)^{N+1}(m_{22} a-m_{12} b)</math>。

贝祖等式中的两个整数分别是<math>s=(-1)^{N+1}m_{22}</math>、<math>t=(-1)^N m_{12}</math>。矩阵法的效率可前文描述的辗转相除法的递归算法是相同的，每一步都有两次乘法和两次加法。

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

: <math>1=su+tw</math>。

两边都乘以''<math>v</math>''：

: <math>v=suv+twv=sL+twv</math>

因为''<math>w</math>''整除等式右边，所以也应整除等式左边的''<math>v</math>''。这个结果叫做[[欧几里得引理]]。<ref name=autogenerated1>Ore, p. 44.</ref>如果一个素数整除''<math>L</math>''那么它至少整除''<math>L</math>''的一个因数。如果一个数''<math>w</math>''互素于数列<math>a_1,a_2,\ldots,a_n</math> 中的每一个数，则''w''也一定互素于它们的乘积<math>a_1\times a_2\times \ldots\times a_n</math>。<ref name=autogenerated1 />

欧几里得引理足以证明每一个自然数的素数分解是惟一的。<ref>Stark, pp. 281–292.</ref>我们用反证法来证明，假设''<math>L</math>''可以分别分解成<math>m</math>个素数和<math>n</math>个素数，即：

: <math>L=p_1p_2\cdots p_m =q_1q_2\cdots q_n</math>

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

=== 线性丢番图方程 ===
[[File:Diophante Bezout.svg|thumb|线性[[丢番图方程]]：<math>9x+12y=483</math>的图像，它的解用蓝点表示。]]

[[丢番图方程]]是以[[亞歷山卓|亚历山大]]数学家[[丢番图]]的名字命名的一类方程，它的解被限制在整数范围。<ref>Rosen, pp. 119–125.</ref>关于整数<math>x</math>和<math>y</math>的线性丢番图方程形如：<ref>Schroeder, pp. 106–107.</ref>

: <math>ax + by = c</math>

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

: <math>ax \equiv c \pmod{b}</math>

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

: <math>sa + tb = g</math>

其中<math>s</math>和<math>t</math>可以用扩展欧几里得算法求解。<ref>Schroeder, pp. 108–109.</ref>所以这个丢番图方程的一个解即是：

: <math>
\begin{align}
x_1 = s ( \frac {c}{g} ) \\
y_1 = t ( \frac {c}{g} )
\end{align}
</math>

总体而言，丢番图方程如果有解，就一定有无数个解。<ref>Rosen, pp. 120–121.</ref>只需要考虑两个解<math>(x_1,y_1)</math> 和<math>(x_2,y_2)</math>：

: <math>ax_1 + by_1 = c = ax_2 + by_2</math>

或者可以写成：

: <math>a(x_1 - x_2) = b(y_2 - y_1)</math>

所以相邻两个解的''<math>x</math>''之间的差是<math>\frac {b}{g}</math>，''<math>y</math>''之间的差是<math>\frac {a}{g}</math>。这样，所有的解都可以表示成：

: <math>
\begin{align}
x = x_1 - \frac{bt}{g} \\
y = y_1 + \frac{at}{g}
\end{align}
</math>

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

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

在这样一个有''<math>
m
</math>''个数的域中，任何非零元素<math>
a
</math>都存在惟一[[乘法逆]] <math>
a^{-1}
</math>使<math>
aa^{-1}=a^{-1}a\equiv 1 \bmod m
</math>。这可以通过解同余式<math>
ax \equiv 1 \bmod m
</math>得出，<ref>Schroeder, pp. 107–109.</ref>或者也可以解与之等价的丢番图方程<ref>Stillwell, pp. 186–187.</ref>

: <math>
ax+my=1
</math>

这个方程可用扩展欧几里得算法解出（参见[[#线性丢番图方程|上文]]）。在[[RSA算法]]中，寻找乘法逆是非常重要的一步，它决定了使用哪个数来解密信息。<ref>Schroeder, p. 134.</ref>虽然RSA算法不使用域而是使用环，扩展欧几里得算法仍然可以用来求乘法逆。欧几里得算法也被应用于[[纠错码]]，例如，它可以代替[[伯利坎普－梅西算法]]解基于有限域的[[BCH码]]和[[里德-所罗门码]]。<ref>"Error correction coding: mathematical methods and algorithms", page 266, Todd K. Moon, John Wiley and Sons, 2005, ISBN 978-0-471-64800-0</ref>

=== 中国剩余定理 ===
辗转相除法也可以用來解线性丢番图方程组。<ref>Rosen, pp. 143–170.</ref>如在[[中国剩余定理]]中，整数可以表示成被<math>
N
</math>个互素的数<math>
m_i
</math>除留下的余数：<ref>Schroeder, pp. 194–195.</ref>

: <math>
\begin{align}
x_1 &\equiv x \pmod{m_1}\\
x_2 &\equiv x \pmod{m_2}\\
\vdots & \\
x_N &\equiv x \pmod{m_N}
\end{align}
</math>

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

: <math> M_i =\frac{M}{m_i} </math>

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

: <math> M_i h_i \equiv 1 \pmod{m_i}</math>

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

: <math> x \equiv (x_1 M_1 h_1 + x_2 M_2 h_2 + \cdots + x_N M_N h_N ) \mod M </math>

因为''<math>
h_i
</math>''是''<math>
M_i
</math>''的乘法逆，所以可以使用扩展欧几里得算法求出（见[[#乘法逆和RSA算法|上一节]]）。

=== 连分数 ===
辗转相除法和[[连分数]]有着紧密的关系。<ref name="Vinogradov_1954">{{cite book | author = [[伊萬·維諾格拉多夫|Vinogradov IM]] | year = 1954 | title = Elements of Number Theory | publisher = Dover | location = New York | pages = 3–13}}</ref>计算连分数的过程如下：

:<math>
\begin{align}
\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{align}
</math>

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

:<math>\frac{a}{b} = q_0 + \frac{1}{q_1 + \frac{r_1}{r_0}} </math>

第三个式子可以代入分母中的<math> \frac{r_1}{r_0} </math>：

:<math>\frac{a}{b} = q_0 + \frac{1}{q_1 + \frac{1}{q_2 + \frac{r_2}{r_1}}} </math>

每一步中，最后一项<math> \frac{r_k}{r_{k-1}} </math>都可以用下一个式子代换，直至最后一个式子，结果是：

:<math>\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 ] </math>

在[[#举例|上文的例子]]中计算了<math> \gcd(1071, 462) </math>，其中商<math> q_k </math>分别是2、3、7，所以分数 <math> \frac{1071}{462} </math> 可以写成如下连分数形式：

:<math>\frac{1071}{462} = 2 + \frac{1}{3 + \frac{1}{7}} = [2; 3, 7]</math>

=== 整数分解算法 ===
计算最大公约数是很多[[整数分解]]算法的重要步骤<ref>{{cite book | author = Crandall R, Pomerance C | year = 2001 | title = Prime Numbers: A Computational Perspective | url = https://archive.org/details/primenumberscomp0000cran | edition = 1st | publisher = Springer-Verlag | location = New York | isbn = 0-387-94777-9 | pages = [https://archive.org/details/primenumberscomp0000cran/page/225 225]–349}}</ref>，如{{le|Pollard's rho算法|Pollard's rho algorithm}}<ref>高德纳, pp. 369–371.</ref>、[[Shor算法]]<ref>{{cite journal | author = [[彼得·秀爾|Shor PW]] | year = 1997 | title = Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer | journal = SIAM J. Sci. Statist. Comput. | volume = 26 | pages = 1484}}</ref>、{{le|Dixon分解法|Dixon's factorization method}}<ref>{{cite journal | author = Dixon JD | year = 1981 | title = Asymptotically fast factorization of integers | url = https://archive.org/details/sim_mathematics-of-computation_1981-01_36_153/page/255 | journal = Math. Comput. | volume = 36 | pages = 255–260 | doi = 10.2307/2007743}}</ref>以及{{le|Lenstra椭圆曲线分解|Lenstra elliptic curve factorization}}<ref>{{cite journal | author = [[亨德里克·倫斯特拉|Lenstra Jr. HW]] | year = 1987 | title = Factoring integers with elliptic curves | url = https://archive.org/details/sim_annals-of-mathematics_1987-11_126_3/page/649 | journal = Annals of Mathematics | volume = 126 | pages = 649–673 | doi = 10.2307/1971363}}</ref>。用辗转相除法算最大公约数效率非常高。而[[连分数分解法]]由于用到了连分数，所以也需要使用辗转相除法<ref>高德纳, pp. 380–384.</ref>。

== 算法效率 ==
[[File:Euclidean algorithm running time X Y.png|thumb|用辗转相除法求 GCD(x,y) 时所需的步数。红点表示所需步骤较少（快），黄、绿、蓝点所需步骤依次增加（慢）。]]

辗转相除法的计算效率已经被彻底研究过了。<ref>高德纳, pp. 339–364.</ref>一个算法的效率可以用计算所需步数乘以每步计算的开销表示。[[加百利·拉梅]]于1884年指出<ref>{{cite journal | author = [[加百利·拉梅]] | year = 1844 | title = Note sur la limite du nombre des divisions dans la recherche du plus grand commun diviseur entre deux nombres entiers | journal = Comptes Rendus Acad. Sci. | volume = 19 | pages = 867–870}}</ref>，用辗转相除法计算两个数的最大公约数所需的步数不会超过其中较小数十進制下的位数<math> h </math>的5倍。<ref>{{cite journal | author = Grossman H | year = 1924 | title = On the Number of Divisions in Finding a G.C.D. | url = https://archive.org/details/sim_american-mathematical-monthly_1924-11_31_9/page/443 | journal = The American Mathematical Monthly | volume = 31 | page = 443 | doi = 10.2307/2298146}}</ref><ref>{{cite book | author = Honsberger R | year = 1976 | title = Mathematical Gems II | publisher = The [[Mathematical Association of America]] | isbn = 0-88385-302-7 | pages = 54–57}}</ref>因为每一步的计算开销通常也是''<math> h </math>''数量级的，所以辗转相除法的[[算法复杂度|复杂度]]是<math> h^2 </math>。

=== 计算步数 ===
计算两个自然数<math> a </math>和<math> b </math>的最大公约数所需的步数可以表示为<math> T(a,b) </math>。<ref name=autogenerated5>高德纳, p. 344.</ref>如果<math> a </math>和<math> b </math>的最大公约数是<math> g </math>，<math> a=mg </math>，<math> b=ng </math>，而<math> m </math>和<math> n </math>是两个互素整数，那么：

: <math> T(a,b)=T(m,n) </math>

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

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

: <math> 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 </math>

其中，根據定义有<math> T(x,0)=0 </math>。<ref name=autogenerated5 />

==== 最差情况 ====

假设用辗转相除法求自然数<math> a </math>和<math> b </math>（<math> a>b>0 </math>）的最大公约数需要<math> N </math>步，那么满足这一条件的<math> a </math>和<math> b </math>的最小值分别是斐波那契数<math> F_{N+2} </math>和<math> F_{N+1} </math>。<ref name=autogenerated6>高德纳, p. 343.</ref>这可以用[[数学归纳法]]证明。<ref>Mollin, p. 21.</ref>假设<math> N=1 </math>，''<math> b </math>''整除''<math> a </math>''，满足这一条件的<math> a </math>和<math> b </math>最小是<math> b=1 </math>、<math> a=2 </math>，正是<math> F_2 </math>和<math> F_3 </math>。现在假设这一规律对<math> M-1 </math>有效。一个需要<math> M </math>步的算法的第一步是<math> a=q_0 b+r_0 </math>，第二步是<math> b=q_1 r_0+r_1 </math>。因为算法是递归的，它需要<math> M-1 </math>步才能算出<math> \gcd(b, r_0) </math>，其中<math> b </math>和<math> r_0 </math>的最小值是<math> F_{M+1} </math>和<math> F_{M} </math>。所以''<math> a </math>''的最小值是当<math> q_0=1 </math>的时候，此时 <math> q=b+r_0=F_{M+1}+F_M=F_{M+2} </math>。1844年，加百利·拉梅发现这个证明标志着[[计算复杂性理论]]的诞生。<ref>LeVeque, p. 35.</ref>这也是[[斐波那契数列]]的第一个实际应用。<ref name=autogenerated6 />

这个结果也证明了辗转相除法的运算步骤不会超过较小数十进制下的位数的五倍。<ref>Mollin, pp. 21–22.</ref>因为如果算法需要''<math> N </math>''步，那么''<math> b </math>''一定大于或等于<math> F_{N+1} </math>，也就是一定大于或等于<math> \varphi^{N-1} </math>，其中<math> \varphi </math>是[[黄金分割比]]。因为<math> b\geq \varphi^{N-1} </math>，所以<math> N-1\leq \log_\varphi b </math>。因为<math> \log_{10}\varphi > \frac{1}{5} </math>，<math> \frac{N-1}{5}<\log_{10}\varphi \log_\varphi b=\log_{10}b </math>，所以<math> N\leq 5 \log_{10} b </math>。所以，辗转相除法不会进行超过[[大O符号|''O''(''h'')]]次除法，其中<math> h </math>是较小数<math> b </math>在十进制下的位数。

==== 平均情况 ====
辗转相除法的平均步骤数有三种不同的定义。第一种定义是计算已知自然数<math> a </math>和从0到<math> a-1 </math>范围内随机选取的自然数''<math> b </math>''的最大公约数所需的时间<math> T(a) </math>：<ref name=autogenerated5 />

:<math>T(a) = \frac{1}{a} \sum_{0 \leq b<a} T(a, b)</math>

但是因为<math> T(a,b) </math>在连续整数间变化非常剧烈，所以<math> T(a) </math>的值也会显得很杂乱。<ref>高德纳, p. 353.</ref>

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

:<math>\tau(a) = \frac{1}{\varphi(a)} \sum_{0 \leq b<a, \mathrm{GCD}(a, b) = 1} T(a, b)</math>

在小于''<math> a </math>''的数中，有<math> \varphi(a) </math>个数与''<math> a </math>''互素，其中<math> \varphi </math>是[[欧拉函数]]。在这个定义中，<math> \tau(a) </math>的函数值增长得平稳很多。<ref>高德纳, p. 357.</ref><ref>{{cite journal | author = Tonkov T | year = 1974 | title = On the average length of finite continued fractions | journal = Acta arithmetica | volume = 26 | pages = 47–57}}</ref>

:<math>\tau(a) = \frac{12}{\pi^2} \ln 2 \ln a + C + O(a^{-\frac{1}{6} + \varepsilon})</math>

誤差項的增長率為<math> O(a^{- \frac{1}{6}+\varepsilon}) </math>，其中<math> \varepsilon </math>是[[无穷小量]]。公式中的常数<math> C </math>等于：

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

其中<math> \gamma </math>是[[欧拉-马歇罗尼常数]]，<math> \zeta' </math>是[[黎曼ζ函数]]的导数。<ref>{{cite journal | author = Porter JW | year = 1975 | title = On a Theorem of Heilbronn | journal = Mathematika | volume = 22 | pages = 20–28}}</ref><ref>{{cite journal | author = 高德纳 DE | year = 1976 | title = Evaluation of Porter's Constant | url = https://archive.org/details/sim_computers-mathematics-with-applications_1976_2/page/137 | journal = Computers and Mathematics with Applications | volume = 2 | pages = 137–139 | doi = 10.1016/0898-1221(76)90025-0}}</ref>公式最左边的<math>\frac{12}{\pi^2}\ln 2</math>由两个独立的方法确定。<ref>{{cite journal | author = Dixon JD | year = 1970 | title = The Number of Steps in the Euclidean Algorithm | journal = J. Number Theory | volume = 2 | pages = 414–422 | doi = 10.1016/0022-314X(70)90044-2}}</ref><ref>{{cite book | author = Heilbronn HA | year = 1969 | chapter = On the Average Length of a Class of Finite Continued Fractions | title = Number Theory and Analysis | editor = Paul Turán | publisher = Plenum | location = New York | id = {{LCCN|68|00|8991}} | pages = 87–96}}</ref>

因为第一种定义可以通过用第二种定义的求和来完成：<ref>高德纳, p. 354.</ref>

:<math>T(a) = \frac{1}{a} \sum_{d | a} \varphi(d) \tau(d)</math>

所以也可以由以下公式近似：<ref name="Norton_1990">{{cite journal | author = Norton GH | year = 1990 | title = On the Asymptotic Analysis of the Euclidean Algorithm | journal = Journal of Symbolic Computation | volume = 10 | pages = 53–58 | doi = 10.1016/S0747-7171(08)80036-3}}</ref>

:<math>T(a) \approx C + \frac{12}{\pi^2} \ln 2 ( \ln a - \sum_{d|a} \frac{\Lambda(d)}{d} )</math>

其中<math> \Lambda(d) </math>是[[冯·曼戈尔特函数]]。<ref>高德纳, p. 355.</ref>

第三种定义<math> Y(n) </math>定义为从1到<math> n </math>间随机选取<math> a </math>和<math> b </math>（[[離散型均勻分佈|均勻分佈]]）时计算它们的最大公约数所需的平均步骤数：<ref name="Norton_1990" />

:<math>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)</math>

将<math> T(a) </math>的近似公式代入，得到<math> Y(n) </math>的近似：<ref>高德纳, p. 356.</ref>

:<math>Y(n) \approx \frac{12}{\pi^2} \ln 2 \ln n + 0.06</math>

=== 每一步的计算开销 ===
在辗转相除法的每一步中，商<math> q_k </math>和余数<math> r_k </math>都通过<math> r_{k-2} </math>和<math> r_{k-1} </math>求出：

: <math> r_{k-2}=q_k r_{k-1}+r_k </math>

所以每一步的计算开销主要与计算商''<math> q_k </math>''的算法有关，因为余数''<math> r_k </math>''可以很迅速地从<math> r_{k-2} </math>、<math> r_{k-1} </math>和''<math> q_k </math>''计算出来：

: <math> r_k=r_{k-2}-q_k r_{k-1} </math>

而计算一个<math> h </math>位整数的除法的算法复杂度是[[大O符号|''O''(''h''(''ℓ''+1))]]，其中''ℓ''<math> l </math>是商的位数。<ref>高德纳, pp. 257–261.</ref>

作为对比，辗转相除法原先的版本使用的是减法，因此效率要慢很多。进行一次除法等同于进行<math> q </math>次减法（其中''<math> q </math>''是商）。如果<math> a </math>和<math> b </math>的比很大，计算出的商也很大，也就需要进行很多次减法。但在另一方面，计算出来的商在大多数情况下都是非常小的，除法中得出一个确定的商''<math> q </math>''的概率大约是<math>\log_2 \left(\frac{u}{u-1}\right)</math>。其中<math> u=(q+1)^2 </math>。<ref>高德纳, p. 352.</ref>比如，商是1、2、3、4的可能性分别是大约41.5%、17.0%、9.3%、5.9%。因为计算机计算减法要快于除法，特別是对于很大的数字<ref>{{cite book | author = Wagon S | year = 1999 | title = Mathematica in Action | publisher = Springer-Verlag | location = New York | isbn = 0-387-98252-3 | pages = 335–336}}</ref>，所以减法版本的辗转相除法的性能可以比得上除法版本。<ref>Cohen, p. 14.</ref>这也被运用于[[二进制]]最大公约数算法。<ref>Cohen, pp. 14–15, 17–18.</ref>

综合考虑算法需要的步数和每一步的计算开销，辗转相除法随两个数字<math> a </math>和<math> b </math>的平均位数成平方级的速度增长（<math> h^2 </math>）。设<math> h_0,h_1,\cdots,h_{N-1} </math>表示计算过程中的余数<math> r_0,r_1,\cdots,r_{N-1} </math>的位数，因为算法的步数<math> N </math>随<math> h </math>线性增长，所以算法的运算时间为：

:<math>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)</math>

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

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

除了辗转相除法之外，也有一些高效的算法存在，如[[二进制最大公约数算法]]将除法操作替换成了[[二进制]]的移位，以进一步提高用计算机运算时的效率。<ref>高德纳, pp. 321–323.</ref><ref>{{cite journal | author = Stein J | year = 1967 | title = Computational problems associated with Racah algebra | journal = Journal of Computational Physics | volume = 1 | pages = 397–405 | doi = 10.1016/0021-9991(67)90047-2}}</ref>但是，这种改变并没有降低算法的复杂度（仍然是[[大O符号|''O''(''h''²)]]），虽然它在计算机上确实比辗转相除法快些。<ref name="Crandall_2001">{{cite book | author = Crandall R, Pomerance C | year = 2001 | title = Prime Numbers: A Computational Perspective | url = https://archive.org/details/primenumberscomp0000cran | edition = 1st | publisher = Springer-Verlag | location = New York | isbn = 0-387-94777-9 | pages = [https://archive.org/details/primenumberscomp0000cran/page/77 77]–79, 81–85, 425–431}}</ref>也可以通过只检視<math> a </math>和<math> b </math>的前几位数来进一步提高效率，不过效果并不明显。<ref>高德纳, p. 328.</ref><ref>{{cite journal | author = Lehmer DH | year = 1938 | title = Euclid's Algorithm for Large Numbers | url = https://archive.org/details/sim_american-mathematical-monthly_1938_45/page/227 | journal = The American Mathematical Monthly | volume = 45 | pages = 227–233 | doi = 10.2307/2302607}}</ref>二进制版的算法还可以扩展到其它进制<ref>{{cite journal | author = Sorenson J | year = 1994 | title = Two fast GCD algorithms | journal = J. Algorithms | volume = 16 | pages = 110–144 | doi = 10.1006/jagm.1994.1006}}</ref>，效率最多可以提升五倍。<ref>{{cite journal | author = Weber K | year = 1995 | title = The accelerated GCD algorithm | journal = ACM Trans. Math. Soft. | volume = 21 | pages = 111–122 | doi = 10.1145/200979.201042}}</ref>

对于超过25,000位数的大数，有一种改进使算法复杂度降低至平方级以下<ref>{{cite book | author = Aho A, Hopcroft J, Ullman J | year = 1974 | title = The Design and Analysis of Computer Algorithms | publisher = Addison–Wesley | location = New York | pages = 300–310}}</ref>，如Schönhage<ref>{{cite journal | author = Schönhage A | title = Schnelle Berechnung von Kettenbruchentwicklungen | journal = Acta Informatica | volume = 1 | pages = 139–144 | doi = 10.1007/BF00289520 | year = 1971}}</ref><ref>{{cite book | author = Cesari G | year = 1998 | chapter = Parallel implementation of Schönhage's integer GCD algorithm | title = Algorithmic Number Theory: Proc. ANTS-III, Portland, OR | url = https://archive.org/details/algorithmicnumbe00buhl | editor = G. Buhler | publisher = Springer-Verlag | location = New York | pages = [https://archive.org/details/algorithmicnumbe00buhl/page/n71 64]–76}} Volume 1423 in ''Lecture notes in Computer Science''.</ref>、Stehlé、Zimmermann等人提出的算法。<ref>{{cite book | author = Stehlé D, Zimmermann P | year = 2005 | chapter = Gal’s accurate tables method revisited | title = Proceedings of the 17th IEEE Symposium on Computer Arithmetic (ARITH-17) | publisher = [[IEEE Computer Society Press]] | location = Los Alamitos, CA}}</ref>这些算法利用2×2的矩阵（见[[#矩阵法|上文]]）。这些亚平方级的算法复杂度通常是<math> O(h(\log h)^2)(\log \log h) </math>。<ref name="Crandall_2001" /><ref>{{cite journal | author = Möller N | title = [http://www.lysator.liu.se/~nisse/archive/sgcd.pdf On Schönhage's algorithm and subquadratic integer gcd computation] | journal = Mathematics of Computation | volume = 77 | pages = 589–607 | doi = 10.1090/S0025-5718-07-02017-0 | year = 2008}}</ref>

== 其他数系 ==
如上文所述，辗转相除法最早用来寻找两自然数的最大公约数，但其实它也可以被推广至实数，甚至是[[多项式]]、[[二次整数]]和[[赫尔维茨四元数]]。在这些数系中，辗转相除法甚至被用来證明一个重要特性：惟一分解，即这些数系中的数能够被惟一地分解成[[不可約元素]]（素数在这些数系的对应物）。惟一分解是数论中很多证明的基础。

=== 有理数和实数 ===
辗转相除法可以被应用至[[实数]]，如欧几里得在[[几何原本]]第10卷中所说的那样。算法的目的是计算出实数<math> g </math>，使已知实数<math> a </math>和<math> b </math>是它的整数倍：<math> a=mg </math>、<math> b=ng </math>，其中<math> m </math>和<math> n </math>是[[整数]]。<ref name="Weil_1983" />这也就找到了<math> a </math>和<math> b </math>的整数关系，即找到整数<math> s </math>和<math> t </math>使<math> sa+tb=0 </math>。欧几里得使用辗转相除法来处理[[通约性|不可通约的长度]]。<ref>{{cite book | author = Boyer CB, Merzbach UC | year = 1991 | title = A History of Mathematics | edition = 2nd | publisher = Wiley | location = New York | isbn = 0-471-54397-7 | pages = 116–117}}</ref><ref>{{cite book | author = [[Florian Cajori|Cajori F]] | year = 1894 | title = A History of Mathematics | url = https://archive.org/details/historyofmathema001062mbp| publisher = Macmillan | location = New York | page = [https://archive.org/details/historyofmathema001062mbp/page/n79 70]}}</ref>

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

: <math> \frac{a}{b}= \frac{mg}{ng}= \frac{m}{n} </math>

于是我们可以写出它的有限[[连分数]]形式：<math> [q_0;q_1,q_2,\cdots,q_n] </math>。如果算法无法结束，那么<math> \frac{a}{b} </math>是[[无理数]]，可以写成无限的连分数形式：<math> [q_0;q_1,q_2,\cdots] </math>。无限连分数的一个例子是：[[黄金分割比]]<math> \varphi=[1;1,1,\cdots] </math>和[[2的算術平方根]]：{{#tag:math|{{根号|2|use math=yes|in math=yes}} = [1; 2, 2, \ldots]}}。通常，算法能够结束的可能性是很低的，因为对于实数<math> a </math>和<math> b </math>，几乎所有<math> \frac{a}{b} </math>都是无理数。

如果算法不结束，也可以在第<math>k</math>步时终止计算，得到近似连分数<math> [q_0;q_1,q_2,\cdots,q_k] </math>。终止时的''<math>k</math>''越大，则近似越准确。连分数<math> \frac{m}{n} </math>的分子和分母互素并满足下式：
: <math>m_k=q_k m_{k-1}+m_{k-2}</math>
: <math>n_k=q_k n_{k-1}+n_{k-2}</math>
其中递归的初始值是<math> m_{-1}=n_{-2}=1 </math>, <math> m_{-2}=n_{-1}=0 </math>。<math> \frac{m_k}{n_k} </math>是<math> \frac{a}{b} </math>在分母是<math> n_k </math>的数中最精确的[[有理数]]近似值：

:<math> 
\left|\frac{a}{b} - \frac{m_k}{n_k}\right| < \frac{1}{n_k^2}
</math>

=== 多项式 ===
只含有一个变量<math> x </math>的多项式可以和整数一样进行加法、乘法和分解為[[不可約多项式]]（也就是多项式中的“素数”）。两个多项式<math> a(x) </math>和<math> b(x) </math>的最大公约数<math> g(x) </math>定义为它们[[因式分解|分解]]之后共有的不可約因式的乘积，这可以用辗转相除法进行计算。<ref name="Lang_1984" >{{cite book | author = [[塞尔日·兰]] | year = 1984 | title = Algebra | url = https://archive.org/details/algebra0000lang | edition = 2nd | publisher = Addison–Wesley | location = Menlo Park, CA | isbn = 0-201-05487-6 | pages = [https://archive.org/details/algebra0000lang/page/190 190]–194}}</ref>对于多项式的算法和整数的算法很相似，在每个步骤''<math>k</math>''，计算出满足以下递归式的商多项式<math> q_k(x) </math>和余数多项式<math> r_k(x) </math>：

:<math> r_{k-2}(x)=q_k(x)r_{k-1}(x)+r_k(x) </math>

其中<math> r_{-2}(x)=a(x) </math>，<math> r_{-1}(x)=b(x) </math>。所选择的商式必须能使<math> q_k(x)r_{k-1}(x) </math>的首项系數和<math> r_{k-2}(x) </math>的相等，这样才能保证每个余数的次数小于前一个余数（<math> \deg[r_k(x)]<\deg[r_{k-1}(x)] </math>）。因为非零多项式的次数是非负整数，并且在每一步都减小，所以辗转相除法的计算一定能在有限步内结束。最后一个非零余数即是两个多项式<math> a(x) </math>和<math> b(x) </math>的最大公约数。<ref>Cox, pp. 37–46.</ref>

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

: <math> a(x)=x^4-4x^3+4x^2-3x+14=(x^2-5x+7)(x^2+x+2) </math>

和

: <math> b(x)=x^4+8x^3+12x^2+17x+6=(x^2+7x+3)(x^2+x+2) </math>.

<math> a(x) </math>除以<math> b(x) </math>得到余数：

:<math>r_0(x) = x^3 + \frac{2}{3} x^2 + \frac{5}{3} x - \frac{2}{3}</math>

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

上文所述的很多应用也适用于多项式。<ref>Schroeder, pp. 254–259.</ref>辗转相除法可以解多项式的线性丢番图方程和中国剩余定理，也可以用来定义多项式的连分数展开式。

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

最后，多项式的系数不必局限于整数、实数、甚至复数。这些系数可以是其他[[域 (数学)|域]]中的元素，如[[#乘法逆和RSA算法|上文]]所述的有限域<math> \mathrm{GF}(p) </math>。从辗转相除法得出的结论也可以直接推广至这类多项式。<ref name="Lang_1984" />

=== 高斯整数 ===
[[File:Gaussian primes.svg|thumb|高斯素数''u''&nbsp;+&nbsp;''vi''在[[复平面]]的分布，其中''u''<sup>2</sup>&nbsp;+&nbsp;''v''<sup>2</sup>小于500。]]

高斯整数是满足<math> \alpha=u+vi </math>的复数，其中<math> u </math>和<math> v </math>是普通[[整数]]，<math> i </math>是[[虚数单位]]（-1的平方根）。<ref name="Stillwell_2003" />通过在高斯整数中定义辗转相除法，根据上文[[#贝祖等式|贝祖等式]]可以证明高斯整数的惟一分解。<ref name="Gauss_1832">{{cite journal | author = [[卡爾·弗里德里希·高斯|Gauss CF]] | date = 1832 | title = Theoria residuorum biquadraticorum | journal = Comm. Soc. Reg. Sci. Gött. Rec. | volume = 4}} See also ''Werke'', '''2''':67–148.</ref>高斯整数的惟一分解性质在很多应用中都很重要，如计算[[勾股数]]或者证明[[费马平方和定理]]。<ref name="Stillwell_2003">{{cite book | author = [[John Stillwell|Stillwell J]] | year = 2003 | title = Elements of Number Theory | publisher = Springer-Verlag | location = New York | isbn = 0-387-95587-9 | pages = 101–116}}</ref>辗转相除法用于这些应用很方便，但并非必不可少，一些定理也可以由其他方式证明。

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

: <math> r_k=r_{k-2}-q_k r_{k-1} </math>

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

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

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

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

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

欧几里得整环的惟一分解性质在很多场合都非常有用。例如，高斯整数的惟一分解性质可以方便地导出[[勾股数]]的公式，或者证明[[费马平方和定理]]。<ref name="Stillwell_2003" />惟一分解性质也是加百利·拉梅于1847年基于[[约瑟夫·刘维尔]]的建议发表的证明[[费马最后定理]]的尝试中的关键部分。<ref>{{cite journal | author = Lamé G | year = 1847 | title = Mémoire sur la résolution, en nombres complexes, de l'équation A<sup>n</sup> + B<sup>n</sup> + C<sup>n</sup> = 0 | journal = J. Math. Pures Appl. | volume = 12 | pages = 172–184}}</ref>拉梅的尝试需要形如<math> x+\omega y </math>的数的惟一分解性质，其中<math> x </math>和<math> y </math>是整数，<math> \omega=e^{\frac{2i\pi}{n}} </math>是1的<math> n </math>次方根，即<math> \omega^n=1 </math>。虽然这对于某些''<math> n </math>''成立（如<math> n=3 </math>时的[[艾森斯坦整数]]），但在其他情况下并非总是正确的。惟一分解性质在[[分圆域]]的失效使[[恩斯特·库默尔]]发明了[[理想数]]的概念，随后[[理查德·戴德金]]创造了[[理想 (环论)|理想]]的概念。{{fact|date=March 2010}}

==== 二次整数的惟一分解 ====

[[File:Eisenstein primes.svg|thumb|艾森斯坦素数<math> u+v\omega </math>在复平面的分布（范数小于500，<math> \omega </math>等于[[1的立方根]]）。]]

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

: <math>\omega = \sqrt{D}</math>

如果''<math> D </math>''等于四的倍数加一，那么：

: <math>\omega = \frac{1 + \sqrt{D}}{2}</math>

如果二次整数环有像[[#高斯整数|上文]]用来比较高斯整数的那样的[[范数 (域论)|范数]]函数，那么它就是规范欧几里德整环。只有当<math> D= </math>&nbsp;−11, −7, −3, −2, −1, 2, 3, 5, 6, 7, 11, 13, 17, 19, 21, 29, 33, 37, 41, 57或73时，二次整数环才是规范欧几里德整环<ref name="Cohn_1962" />。<math> D= </math>&nbsp;−1和−3时的二次整数分别叫作[[高斯整数]]和[[艾森斯坦整数]]。

但如果[[范数 (域论)|范数]]函数<math> f </math>可以是任何欧几里得函数，那么使二次整数环是欧几里得整环的''<math> D </math>''的可能值到目前为止还不确定。<ref name="Clark_1994">{{cite journal | author = Clark DA | year = 1994 | title = [http://www.springerlink.com/content/6t9u2440402n1346/ A quadratic field which is Euclidean but not norm-Euclidean] | journal = Manuscripta mathematica | volume = 83 | pages = 327–330 | doi = 10.1007/BF02567617}}</ref>是欧几里得整环但不是规范欧几里德整环的第一个例子（<math> D=69 </math>）发表于1994年<ref name="Clark_1994" />。温伯格於1973年证明，在[[广义黎曼猜想]]成立的前提下，<math> D>0 </math>时的二次整数环是欧几里得整环，當且僅當它是一个[[主理想环]]。<ref>{{cite journal | author = Weinberger P | chapter = On Euclidean rings of algebraic integers | journal = Proc. Sympos. Pure Math. | volume = 24 | pages = 321–332}}</ref>

=== 非交换环 ===
辗转相除法也可以应用至非交换环，如[[赫尔维茨四元数]]。<ref>{{cite book | author = [[John Stillwell|Stillwell J]] | year = 2003 | title = Elements of Number Theory | publisher = Springer-Verlag | location = New York | isbn = 0-387-95587-9 | pages = 151–152}}</ref>令<math> \alpha </math>和<math> \beta </math>表示这样一个环中的两个元素。他们有右公约数<math> \delta </math>如果<math> \alpha=\xi\delta </math>, <math> \beta=\eta\delta </math>（<math> \xi </math>和<math> \eta </math>是环中的元素）。同样，他们有左公约数''<math> \delta </math>''如果<math> \alpha=\delta\zeta </math>, <math> \beta=\delta\eta </math>（<math> \xi </math>和<math> \eta </math>是环中的元素）。因为乘法不符合交换律，也就有两个版本的辗转相除法，一个计算右公约数，一个计算左公约数。例如对于右公约数，辗转相除法求最大公约数的第一步可以写成：

: <math> \rho_0=\alpha-\psi_0\beta=(\zeta-\psi_0\eta)\delta </math>

其中<math> \psi_0 </math>是商，<math> \rho_0 </math>是余数。对于左公约数，第一步过程是：

:<math> \rho_0=\alpha-\beta\psi_0=\delta(\zeta-\eta\psi_0) </math>

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

由辗转相除法得出的大多数结果都适用于非交换环。例如，[[贝祖等式]]表明最大右公约数可以表示成{{math|1=α}}的倍数和{{math|1=β}}的倍数的和，即，存在<math> \sigma </math>和<math> \tau </math>使：

:<math> \Gamma_\text{右 }=\sigma\alpha+\tau\beta </math>

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

:<math> \Gamma_\text{左 }=\alpha\sigma+\beta\tau </math>

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

== 推广至其他数学结构 ==
[[File:TorusKnot3D.png|thumb|辗转相除法可以推广至[[纽结理论]]。<ref>{{cite journal | author = Yamada Y | year = 2007 | title = [http://arxiv.org/abs/0708.2316 Generalized rational blow-down, torus knots, and Euclidean algorithm] | publisher = arXiv:0708.2316v1}}</ref>]]

辗转相除法有三个性质保证它不会永远进行下去。第一，它可以写成一系列递归式：

: <math> r_k=r_{k-2}-q_k r_{k-1} </math>

其中每一个余数都比前一个余数小，<math> |r_k| < |r_{k-1}| </math>。第二，余数的大小有嚴格下限，如<math> |r_k|\geq 0 </math>。第三，小于<math> |r_k| </math>的数的数量是有限的。辗转相除法推广至其他数学结构，如{{link-en|纏結|tangle (mathematics)}}<ref>{{cite book| author = [[約翰·何頓·康威|John Horton Conway]]|contribution=An enumeration of knots and links, and some of their algebraic properties|publisher=Pergamon|year=1970|pages=329–358|title=Computational Problems in Abstract Algebra (Proc. Conf., Oxford, 1967)}}</ref>和[[超限数|超限]][[序数]]<ref>{{cite journal | author = Jategaonkar AV | year = 1969 | title = [http://projecteuclid.org/euclid.bams/1183530557 Rings with transfinite left division algorithm] | journal = Bull. Amer. Math. Soc. | volume = 75 | pages = 559–561 | doi = 10.1090/S0002-9904-1969-12242-1}}</ref>时仍保持这种性质。

辗转相除法的一个重要推广是[[代数几何]]中[[格罗布纳基]]的概念。像前文所述，<math> a </math>和<math> b </math>的最大公约数<math> g </math>是它们的[[理想 (环论)|理想]]的生成元素。也就是说，对任何整数<math> s </math>和<math> t </math>，存在另一个整数<math> m </math>使：

: <math> sa+tb=mg </math>

虽然这对一元多项式也成立，但是对多元多项式就不成立了。<ref>Cox, p. 65.</ref>在多元多项式的情况下，生成元素的有限集合<math> g_1,g_2,\cdots </math>可以定义如下：

: <math> sa+tb=\mathrm{\sum}_k m_kg_k </math>

其中''<math> s </math>''、''<math> t </math>''和<math> m_k </math>是多元多项式。<ref>Cox, pp. 73–79.</ref>任何这样的多元多项式<math> f </math>可以表示成生成多项式的和加上惟一的余数多项式<math> r </math>, 通常叫做多项式''<math> f </math>''的一般形式。

: <math> f=r+\mathrm{\sum}_k q_kg_k </math>

虽然商多项式<math> q_k </math>可能不惟一。<ref>Cox, pp. 79–86.</ref>这些生成多项式的集合就叫做格罗布纳基。<ref>Cox, p. 74.</ref>

== 参考文献 ==
=== 引用 ===
{{Reflist|30em}}

=== 来源 ===
{{refbegin}}
; 书籍
* {{en}}{{cite book | author = [[Henri Cohen|Cohen H]] | year = 1993 | title = A Course in Computational Algebraic Number Theory | url = //books.google.com/books?id=hXGr-9l1DXcC | publisher = Springer-Verlag | location = New York | isbn = 0-387-55640-0 | access-date = 2022-07-25 | archive-date = 2019-05-03 | archive-url = https://web.archive.org/web/20190503002439/https://books.google.com/books?id=hXGr-9l1DXcC }}
* {{en}}{{cite book | author = Cohn H | year = 1962 | title = Advanced Number Theory | url = //books.google.com/books?id=yMGeElJ8M0wC | publisher = Dover | location = New York | isbn = 0-486-64023-X | access-date = 2022-07-25 | archive-date = 2019-05-02 | archive-url = https://web.archive.org/web/20190502175006/https://books.google.com/books?id=yMGeElJ8M0wC }}
* {{en}}{{cite book |author = [[Thomas H. Cormen|Cormen TH]], [[Charles E. Leiserson|Leiserson CE]], [[Ronald L. Rivest|Rivest RL]], and [[Clifford Stein|Stein C]] |year = 2001 |title = Introduction to Algorithms |url = //books.google.com/books?id=NLngYyWFl_YC |edition = 2nd |publisher = MIT Press and McGraw–Hill |isbn = 0262032937 |access-date = 2022-07-25 |archive-date = 2021-04-14 |archive-url = https://web.archive.org/web/20210414095051/https://books.google.com/books?id=NLngYyWFl_YC }}
* {{en}}{{cite book | author = Cox D, Little J, and O'Shea D | year = 1997 | title = Ideals, Varieties, and Algorithms: An Introduction to Computational Algebraic Geometry and Commutative Algebra | url = //books.google.com/books?id=7eLkq0wQytAC | edition = 2nd | publisher = Springer-Verlag | isbn = 0-387-94680-2 | access-date = 2022-07-25 | archive-date = 2019-05-02 | archive-url = https://web.archive.org/web/20190502232408/https://books.google.com/books?id=7eLkq0wQytAC }}
* {{en}}{{cite book | author = [[约翰·彼得·古斯塔夫·勒热纳·狄利克雷|狄利克雷]] |year=1894 | title = Vorlesungen über Zahlentheorie | url = https://archive.org/details/vorlesungenber00lejeuoft |editor=[[理查德·戴德金|Richard Dedekind]] |publisher=Vieweg |location=Braunschweig }}
* {{en}}{{cite book | author = [[戈弗雷·哈罗德·哈代]], [[愛德華·梅特蘭·賴特|Wright EM]] [revised by D.R. Heath-Brown and J.H. Silverman]. | date = 2008 | url = //books.google.com/books?id=rey9wfSaJ9EC | title = An Introduction to the Theory of Numbers | edition = 6th | publisher = Clarendon Press | location = Oxford | isbn = 0199219869 | access-date = 2022-07-25 | archive-date = 2021-04-15 | archive-url = https://web.archive.org/web/20210415215516/https://books.google.com/books?id=rey9wfSaJ9EC }}
* {{en}}{{cite book |author=[[高德纳]] |year=1997 |title=The Art of Computer Programming（[[计算机程序设计艺术]]）, Volume 2: Seminumerical Algorithms|edition=3rd|publisher=Addison–Wesley |isbn = 0201896842 }}
* {{en}}{{cite book | author = [[William J. LeVeque|LeVeque WJ]] | year = 1977 | title = Fundamentals of Number Theory | publisher = Dover | location = New York | isbn = 0-486-68906-9}}
* {{en}}{{cite book | author = Mollin RA | year = 2008 | title = Fundamental Number Theory with Applications | edition = 2nd|publisher=Chapman & Hall/CRC|location=Boca Raton|isbn = 9781420066593}}
* {{en}}{{cite book | author = [[Øystein Ore|Ore Ø]] | date = 1948 | title = Number Theory and Its History | url = https://archive.org/details/numbertheoryitsh00ore| publisher = McGraw–Hill | location = New York | isbn = 0486656209 }}
* {{en}}{{cite book | author = Rosen KH | year = 2000 | title = Elementary Number Theory and its Applications | edition = 4th | publisher = Addison–Wesley | location = Reading, MA |isbn = 0201870738 }}
* {{en}}{{cite book | author = [[Manfred R. Schroeder|Schroeder MR]] | year = 2005 | title = Number Theory in Science and Communication | edition = 4th | publisher = Springer-Verlag |isbn= 0387158006 }}
* {{en}}{{cite book | author = [[Harold Stark|Stark H]] | year = 1978 | title = An Introduction to Number Theory | url = https://archive.org/details/introductiontonu00star_0| publisher = MIT Press | isbn = 0-262-69060-8 }}
* {{en}}{{cite book | author = [[John Stillwell|Stillwell J]] | year = 1997 | title = Numbers and Geometry | publisher = Springer-Verlag | location = New York | isbn = 0-387-98289-2 }}
* {{en}}{{cite book | author = Tattersall JJ | year = 2005 | title = Elementary number theory in nine chapters | url = https://archive.org/details/elementarynumber0000jame | publisher = [[劍橋大學出版社|Cambridge University Press]] | location = Cambridge | isbn = 9780521850148}}
* {{en}}{{cite book | author1 = Uspensky JV |author2 = Heaslet MA | year = 1939 | title = Elementary Number Theory | publisher = McGraw–Hill | location = New York | isbn = 0070667500 }}
{{refend}}

== 外部链接 ==
{{Commonscat|Euclidean algorithm}}
{{Portal|数学}}
* [http://www.math.sc.edu/~sumner/numbertheory/euclidean/euclidean.html Demonstrations of Euclid's algorithm] {{Wayback|url=http://www.math.sc.edu/~sumner/numbertheory/euclidean/euclidean.html |date=19980113040536 }}
* {{MathWorld | urlname=EuclideanAlgorithm | title=Euclidean Algorithm}}
* [http://www.cut-the-knot.org/blue/Euclid.shtml Euclid's Algorithm] {{Wayback|url=http://www.cut-the-knot.org/blue/Euclid.shtml |date=20060404100134 }} at [[cut-the-knot]]
* {{PlanetMath | urlname=EuclidsAlgorithm | title=Euclid's algorithm}}
* [http://www.mathpages.com/home/kmath384.htm The Euclidean Algorithm] {{Webarchive|url=http://arquivo.pt/wayback/20160515140122/http%3A//www.mathpages.com/home/kmath384.htm |date=2016-05-15 }} at MathPages
* [http://www.cut-the-knot.org/blue/EuclidAlg.shtml Euclid's Game] {{Wayback|url=http://www.cut-the-knot.org/blue/EuclidAlg.shtml |date=20060420142707 }} at [[cut-the-knot]]
* [http://plus.maths.org/issue40/features/wardhaugh/index.html Music and Euclid's algorithm] {{Wayback|url=http://plus.maths.org/issue40/features/wardhaugh/index.html |date=20070809225041 }}

{{数论算法}}

[[Category:数论算法]]
[[Category:数论]]
[[Category:带有伪代码示例的条目]]
[[Category:带有代码示例的条目]]