輾轉相除法

维基百科,自由的百科全书
跳转至: 导航搜索
辗转相除法的演示动画:两条线段分别表示252和105,其中每一段表示21。动画演示了循环从大数中减去小数,直到其中一段的长度为0,此时剩下的一条线段的长度就是252和105的最大公约数。

数学中,辗转相除法,又称欧几里得算法,是求最大公约数的算法。辗转相除法首次出现于欧几里得的《几何原本》(第VII卷,命题i和ii)中,而在中国则可以追溯至东汉出现的《九章算术》。

两个整数的最大公约数是能够同时整除它们的最大的正整数。辗转相除法基于如下原理:两个整数的最大公约数等于其中较小的数和两数的差的最大公约数。例如,252和105的最大公约数是21(252 = 21 × 12105 = 21 × 5);因为252 − 105 = 147,所以147和105的最大公约数也是21。在这个过程中,较大的数缩小了,所以继续进行同样的计算可以不断缩小这两个数直至其中一个变成零。这时,所剩下的还没有变成零的数就是两数的最大公约数。由辗转相除法也可以推出,两数的最大公约数可以用两数的整数倍相加来表示,如21 = 5 × 105 + (−2) × 252。这个重要的等式叫做贝祖等式

辗转相除法最早出现在欧几里得几何原本中(大约公元前300年),所以它是现在仍在使用的算法中最早出现的。这个算法原先只用来处理自然数,但在19世纪,辗转相除法被推广至其他类型的数,如高斯整数和一元多项式。自此,现代抽象代数概念如欧几里得整环开始出现。后来,辗转相除法又扩展至其他数学领域,如纽结理论和多元多项式。

辗转相除法有很多应用,它甚至可以用来生成全世界不同文化中的传统音乐节奏。[1]在现代密码学方面,它是RSA算法(一种在电子商务中广泛使用的公钥加密算法)的重要部分。它还被用来解丢番图方程,寻找满足中国剩余定理的数,或者求有限域中元素的逆。辗转相除法还可以用来构造连分数,在施图姆定理和一些整数分解算法中也有应用。辗转相除法是现代数论中的基本工具。

辗转相除法处理大数时非常高效,如果用除法而不是减法实现,它需要的步骤不会超过较小数的位数(十进制下)的五倍。拉梅于1844年证明了这点,开创了计算复杂性理论

背景[编辑]

最大公约数[编辑]

欧几里得的辗转相除法计算的是两个自然数ab的最大公约数g,意思是能够同时整除ab的自然数中最大的一个。两个数的最大公约数通常写成GCD(a, b),或者简写成(a, b),[2]但是第二种写法也被使用在其他数学概念,如二维向量的坐标。

如果GCD(ab) = 1,那么ab互素[3]ab是否互素和它们是否素数无关。[4]如,6和35都不是素数,因为它们都可以分解为多于一个素因数的乘积:\displaystyle 6=2 \times 3\displaystyle 35=5 \times 7。但是,6和35互素,因为除了1以外没有自然数同时整除6和35。

一个24×60的长方形正好被十个12×12的方格填满,其中12是24和60的最大公约数。一般地,当且仅当cab的公约数时,a×b尺寸的长方形可被边长c的正方形正好填满。

g = GCD(a, b)。由于ab都是g的整数倍,所以可以写成a = mgb = ng,并且不存在更大的整数G > g使等式成立。为了使g尽可能大,就要使ab中所有公约数都提取出来归入g中,所以自然数mn一定互素,并且ab的最大公约数g可以被ab的所有其他公因数c整除。[5]

我们可以用右图来解释最大公约数的概念:[6]一个长方形的边长为ab。因为ab的任何公约数c都可以整除ab,所以长方形的边可以等分为长度为c的线段,也就是长方形可以被边长为c的正方形正好填满。而最大公约数g是所有可能的c中最大的一个。例如,一个24 × 60的长方形区域可以分成1 × 1、2 × 2、3 × 3、6 × 6或12 × 12的正方形网格。也就是说,12是24和60的最大公约数。

ab的最大公约数是两数共有的素因数的乘积。[7]例如,462可以分解成2 × 3 × 7 × 11;1071可以分解成3 × 3 × 7 × 17。462和1071的最大公约数等于它们共有的素因数的乘积3 × 7 = 21。如果两数没有公共的素因数,那么它们的最大公约数是1,也即这两个数互素。辗转相除法的优点就是可以不必计算出所有素因数的前提下高效地求出最大公约数,[8][9]因为大数的素因数分解对于现代的计算机而言非常困难,因而被许多加密系统使用。[10]

在数学中,尤其是高等数学环论中,最大公约数有一个更加巧妙的定义:[11]ab的最大公约数gab的线性和中(绝对值)最小的一个,即所有形如ua + vb(其中uv是整数)的数中(绝对值)最小的数。所有ua + vb都是g的整数倍(ua + vb = mg,其中m是整数)。在现代数学语言中,ab构成的理想g生成的主理想。最大公约数的这个定义和其他定义的等价将在下面描述。

三个数的最大公约数的定义和两个数的相同,即是它们共有的素因数的积,[12]它们或者也可以按下式计算[13]

GCD(a, b, c) = GCD(a, GCD(b, c)) = GCD(GCD(a, b), c) = GCD(GCD(a, c), b).

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

归纳、递归和无穷递降[编辑]

与此算法相关的数学方法是数学归纳法递归无穷递降。数学归纳法[14]经常用来证明关于所有自然数的定理:[15]假设定理对自然数n成立,证明它对自然数n + 1成立;然后再证明定理对一个特定的数n0成立(通常是1),那么定理对所有大于n0的自然数成立。递归[16]是将相关的数组成一个数列a1a2a3……),[17]其中每一项都用前一项或前几项表示。如斐波那契数列就是递归的,每一项Fn都等于Fn−1 + Fn−2。辗转相除法中的一些等式也是递归的。最后,无穷递降[18]是用方程的一个自然数解导出比它小的自然数解。[19]但是,这种转化不能永远进行下去,因为存在一个最小的自然数。这将证明辗转相除法一定会在有限步内结束。[20]

算法描述[编辑]

计算过程[编辑]

辗转相除法是一种递归算法,每一步计算的输出值就是下一步计算时的输入值。[21]k表示步骤数(从0开始计数),算法的计算过程如下。

每一步的输入是都是前两次计算的余数rk−1rk−2。因为每一步计算出的余数都在不断减小,所以,rk−1小于rk−2。在第k步中,算法计算出满足以下等式的qk余数 rk

rk−2 = qk rk−1 + rk

其中rk < rk−1。也就是rk−2要不断减去rk−1直到比rk−1小。

在第一步计算时(k = 0),设r−2r−1分别等于ab,第2步(此时k = 1)时计算r−1(即b)和r0(第一步计算产生的余数)相除产生的商和余数,以此类推。整个算法可以用如下等式表示:

a = q0 b + r0
b = q1 r0 + r1
r0 = q2 r1 + r2
r1 = q3 r2 + r3

如果输入参因为a < b,所以ab相除得到的商q0等于0,余数r0等于a。所以在运算的每一步中得出的余数一定小于上一步计算的余数(rk一定小于rk−1)。

由于每一步的余数都在减小并且不为负数,必然存在第N步时rN等于0,使算法终止,[20]rN−1 就是ab的最大公约数。其中N不可能无穷大,因为在r0和0之间只有有限个自然数。

正确性的证明[编辑]

辗转相除法的正确性可以用两步来证明。[21]首先,算法的最终结果rN−1同时整除ab。因为它是一个公约数,所以必然小于或者等于最大公约数g。然后,任何ab的公约数都能整除rN−1。所以g一定小于或等于rN−1。两个不等式只在rN−1 = g是同时成立。具体证明如下:

  1. 证明rN−1同时整除ab
    因为余数rN是0,rN−1能够整除rN−2
    rN−2 = qN rN−1
    因为rN−1能够整除rN−2,所以也能够整除rN−3
    rN−3 = qN−1 rN−2 + rN−1
    同理可证rN−1可以整除所有之前步骤的余数,包括ab,即rN−1ab的公约数,rN−1 ≤ g
  2. 证明任何整除ab的自然数g(也就是ab的公约数)都能整除rN-1
    根据定义,ab可以写成g的倍数:a = mgb = ng,其中mn是自然数。因为r0 = a − q0b = mg − q0ng = (m − q0n)g,所以g整除r0。同理可证g整除每个余数r1r2……rN-1。所以,最大公约数g一定整除rN−1,因而g ≤ rN−1

因为第一步的证明告诉我们rN−1 ≤ g,所以g = rN−1。即:[22][23]

g = GCD(a, b) = GCD(b, r0) = GCD(r0, r1) = … = GCD(rN−2, rN−1) = rN−1

举例[编辑]

算法的演示动画。最初的绿色矩形的长和宽分别是a = 1071、b = 462,从中不断铺上462×462的正方形直到剩下部分面积是462×147;然后再铺上147×147的正方形直至剩下21×147的面积;最后,铺上21×21的正方形时,绿色部分就没有了。即21是1071和462的最大公约数.

例如,计算a = 1071和b = 462的最大公约数的过程如下:从1071中不断减去462直到小于462(可以减2次,即商q0 = 2),余数是147:

1071 = 2 × 462 + 147.

然后从462中不断减去147直到小于147(可以减3次,即q1 = 3),余数是21:

462 = 3 × 147 + 21.

再从147中不断减去21直到小于21(可以减7次,即q2 = 7),没有余数:

147 = 7 × 21 + 0.

此时,余数是0,所以1071和462的最大公约数是21,这和用素因数分解得出的结果相同(见上文)用表格表示如下:

步骤数 算式 商和余数
0 1071 = 462 q0 + r0 q0 = 2、r0 = 147
1 462 = 147 q1 + r1 q1 = 3、r1 = 21
2 147 = 21 q2 + r2 q2 = 7、r2 = 0(算法终止)

图形演示[编辑]

辗转相除法的计算过程可以用图形演示。[24]假设我们要在a×b矩形地面上铺正方形瓷砖,并且正好铺满,其中a大于b。我们先尝试用b×b的瓷砖,但是留下了r0×b的部分,其中r0<b。我们接着尝试用r0×r0的正方形瓷砖铺,又留下了r1×r0的部分,然后再使用r1×r1的正方形铺……直到全部铺满为止,即到某步时正方形刚好覆盖剩余的面积为止。此时用到的最小的正方形的边长就是原来矩形的两条边长的最大公约数。在图中,最小的正方形面积是21×21(红色),而原先的矩形(绿色)边长是是1071×462,所以21是1071和462的最大公约数。

计算商和余数[编辑]

在每个步骤k中,辗转相除法都需要计算两个数rk−1rk−2的商qk和余数rk

rk−2 = qk rk−1 + rk

其中rk绝对值小于rk−1。除法的算法保证这样的商和余数总是存在。自然数的除法算法还指出这样的商和余数是惟一的,但这对辗转相除法而言并非必要。[25]

在欧几里得最初的描述中,商和余数是通过连续的减法来计算的,即从rk−2中不断减去rk−1直到小于rk−1。但是现在通常使用更高效的除法和模除来计算商和余数:

rk rk−2 mod rk−1

计算机实现[编辑]

辗转相除法可用伪代码表示如下[26]

function gcd(a, b)
    while b ≠ 0
       t ← b
       b ← a mod b
       a ← t
    return a

在第k次循环开始时,变量b的值是前一次运算的余数rk−1,变量a的值是再前一次运算的余数rk−2。步骤b := a mod b的作用等同于递归式rkrk−2 mod rk−1。变量t的功能是在下一个余数rk计算过程中临时性地保存rk−1的值。在一次循环结束时,变量b的值是前一次运算的余数rk,变量a的值是再前一次运算的余数rk−1

在欧几里得定义的减法版本,取餘运算被减法替换。[27]

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

变量ab的值分别是前两次的余数rk−1rk−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]

function gcd(a, b)
    if b = 0
       return a
    else
       return gcd(b, a mod 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 = qk rk−1 + rk

假设rk−1 > rk > 0,使用以下式子计算一个负的余数ek

rk−2 = (qk + 1) rk−1 + ek

如果|ek| < |rk|,那么用ek替换rk进行下一次运算。如利奥波德·克罗内克所指出的,这个版本需要的运算步骤是欧几里得算法的所有实现中最少的。[29][30]

历史发展[编辑]

辗转相除法可能在欧几里得之前几个世纪就已经有了。图为使用两脚规进行测量。

辗转相除法是目前仍然在使用的历史最悠久的算法之一。[31]它首次出现于几何原本(卷7命题1–2、卷10命题2–3)(大约公元前300年)。在卷7中用于整数,在卷10中用于线段的长度(也就是现在所说的实数,但是当时未有实数的概念)。卷10中出现的算法是几何的,两段线段ab的最大公约数是准确测量ab的最大长度。

这个算法可能并非欧几里得发明,而仅仅是将先人的结果编进他的几何原本。[32][33]数学家、历史学家范德瓦尔登英语Bartel Leendert van der Waerden认为卷7的内容可能来自毕达哥拉斯学院出身的数学家写的关于数论的教科书。[34]辗转相除法可能是被大约公元前375年的尤得塞斯发现的,[31][35]但也有可能更早之前就已经存在,[36][37]因为欧几里得和亚里士多德的著作中都出现了ἀνθυφαίρεσις一词(anthyphairesis, 意为“辗转相减”)。[38]

几个世纪之后,辗转相除法又分别被中国人和印度人独立发现,[39]主要用来解天文学中用到的丢番图方程以及指定准确的历法。5世纪末,印度数学家天文学家阿里亚哈塔可能是因为辗转相除法在解丢番图方程时的高效率[40]而称它为“粉碎机”。[41]因为在中国,九章算术中提到了一种类似辗转相减法的“更相减损术”[42],而孙子算经中出现了此算法的一个特例中国剩余定理[43]但是辗转相除法的完整表述直到1247年秦九韶数学九章中才出现。在欧洲,辗转相除法首次出现于克劳德·巴希特英语Claude Gaspard Bachet de Méziriac的著作Problèmes plaisants et délectables的第二版[44]在欧洲,辗转相除法广泛使用于丢番图方程和连分数。后来,英国数学家桑德森英语Nicholas Saunderson扩展欧几里得算法作为罗杰科茨英语Roger Cotes对计算连分数的方法的研究发表。[45]

19世纪,辗转相除法孕育出了一些新的数系,如高斯整数艾森斯坦整数。1815年,高斯用辗转相除法证明高斯整数的分解是惟一的,他的研究发表于1832年。[46]高斯在他的算数研究(published 1801)中,作为处理连分数的方法提到了这个算法。[39]约翰·狄利克雷是第一个将辗转相除法作为数论的基础的数学家。[47]狄利克雷提出,数论中的很多结论,如分解的惟一性,在任何使辗转相除法成立的数系中有效。[48]狄利克雷的观点被理查德·戴德金修改和推广,他用辗转相除法研究代数整数。戴德金是第一个用高斯整数的分解惟一性证明费马平方和定理的数学家。[49]戴德金还率先定义了欧几里得整环的概念。19世纪末,辗转相除法的辉煌逐渐被戴德金的理想取代。[50]

"欧几里得算法是所有算法的鼻祖,因为它是现存最古老的非凡算法。"

高德纳, 计算机程序设计艺术,第二卷:半数值算法,第二版 (1981), p. 318.

辗转相除法的其他应用发展于19世纪。1829年,施图姆将辗转相除法用于施图姆序列(用于确定多项式的不同实根的个数的方法)。[51]

辗转相除法是历史上第一个整数关系算法英语integer relation algorithm,即寻找两数的整数关系的算法。近年来,出现了一些新颖的整数关系算法,如埃拉曼·弗格森英语Helaman Ferguson和福尔卡德于1979年发表的弗格森-福尔卡德算法英语[52]以及与它相关的LLL算法英语Lenstra–Lenstra–Lovász lattice basis reduction algorithmHJLS算法以及PSLQ算法英语PSLQ algorithm[53][54]

1969年,科尔(Cole)和戴维(Davie)基于辗转相除法创造了一种二人游戏,叫做欧几里得游戏[55]这个游戏有最优策略。[56]游戏开始于两列分别为ab个棋子组成的序列,玩家轮流从较长一列中取走较短一列棋子数量的m倍的棋子。如果两列棋子ab分别由xy个棋子组成,其中x大于y,那么玩家可以序列a的棋子数量减少为自然数xmy。最后率先将一列棋子清空的玩家胜出。[57][58]

数学上的应用[编辑]

贝祖等式[编辑]

贝祖等式说明,两个数ab的最大公约数g可以表示为ab的线性和。[59]也就是说,存在整数st使g = sa + tb[60][61]

整数st可以从辗转相除法算出的商q0q1……计算出。[62] 从辗转相除法的最后一步开始,g可以表示成前一步的商qN−1和前两步的余数rN−2rN−3

g = rN−1 = rN−3qN−1 rN−2

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

rN−2 = rN−4qN−2 rN−3
rN−3 = rN−5qN−3 rN−4

将这两行式子代入第一个式子,可以将g表示成rN−4rN−5的线性和。重复进行迭代直到出现ab:

r2 = r0q2 r1
r1 = bq1 r0
r0 = aq0 b

最终,g可以表示成ab的线性和:g = sa + tb贝祖等式以及以上证明都可以扩展至欧几里得整环

主理想和相关问题[编辑]

贝祖等式提供了另一种定义ab的最大公约数g的方法。[11]考虑形如ua + vb(其中uv是整数)的数的集合。因为ab都可以被g整除,所以这个集合中的所有元素都可以被g整除。也就是说这个集合中的数都可以表示成g的倍数,或者ab的其他公约数的倍数。但是,只有最大公约数才是这个集合的元素。根据贝祖等式,当u = sv = t时得出g。任何其他的公约数都不是这个集合的元素,因为它们都不能被比它们大的g整除。相反地,g的任何倍数都属于这个集合,只要令u = msv = mt,其中st是贝祖等式中的整数:

mg = msa + mtb

所以,形如ua + vb的数的集合等于g的整数倍的集合。也就是说,任意两个数的线性和的集合等同于它们最大公约数的整数倍的集合。ab的最大公约数叫做ab理想的生成元素。这个最大公约数的定义导出了现代抽象代数的概念:主理想(由单个元素生成的理想)以及主理想整环(仅由主理想构成的整环)。

这个结果可以解决很多问题。[63]例如,考虑两个容积分别为ab的量杯。通过量取u倍第一个量杯的体积以及v倍第二个量杯的体积液体,任何体积为ua + vb的液体都可以被量出,可以被量出的液体的体积g一定是ab的最大公约数。

扩展欧几里得算法[编辑]

贝祖等式的整数st可以通过扩展欧几里得算法算出。这个扩展算法在原有辗转相除法的基础上增加了两个递归等式:[64]

sk = sk−2qksk−1
tk = tk−2qktk−1

算法开始时:

s−2 = 1, t−2 = 0
s−1 = 0, t−1 = 1

加上这个递归式后,当算法终止于rN = 0,贝祖等式的整数st分别由sNtN给出。

这个算法的正确性可以用数学归纳法来证明。假设递归至第k−1步是正确的,也就是假设:

rj = sj a + tj b

对所有j小于k成立。则第k步运算得出以下等式:

rk = rk−2qkrk−1

因为rk−2rk−1被假定是正确的,所以可以用st表示:

rk = (sk−2 a + tk−2 b) − qk(sk−1 a + tk−1 b)

整理后得到第k步的结果,和我们期望得到的结果一致:

rk = sk a + tk b = (sk−2qksk−1) a + (tk−2qktk−1) b

矩阵法[编辑]

整数st也可以用矩阵运算得出。[65]辗转相除法的计算过程:

a = q0 b + r0
b = q1 r0 + r1
rN−2 = qN rN−1 + 0

可以写作2×2的商矩阵乘以一个2维余数向量:


\begin{pmatrix} a \\ b \end{pmatrix} =
\begin{pmatrix} q_{0} & 1 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} b \\ r_{0} \end{pmatrix} =
\begin{pmatrix} q_{0} & 1 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} q_{1} & 1 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} r_{0} \\ r_{1} \end{pmatrix} =
\cdots =
\prod_{i=0}^{N} \begin{pmatrix} q_{i} & 1 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} r_{N-1} \\ 0 \end{pmatrix}

M表示所有商矩阵的乘积:


\mathbf{M} = \begin{pmatrix} m_{11} & m_{12} \\ m_{21} & m_{22} \end{pmatrix} =
\prod_{i=0}^{N} \begin{pmatrix} q_{i} & 1 \\ 1 & 0 \end{pmatrix} =
\begin{pmatrix} q_{0} & 1 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} q_{1} & 1 \\ 1 & 0 \end{pmatrix} \cdots \begin{pmatrix} q_{N} & 1 \\ 1 & 0 \end{pmatrix}

这使辗转相除法化简为:


\begin{pmatrix} a \\ b \end{pmatrix} =
\mathbf{M} \begin{pmatrix} r_{N-1} \\ 0 \end{pmatrix} =
\mathbf{M} \begin{pmatrix} g \\ 0 \end{pmatrix}

为了用ab的线性和表示g,等式两边同时乘以矩阵M逆矩阵[65][66]M行列式等于(−1)N+1,因为它等于商矩阵的行列式的乘积,其中每一个因式都是−1。因为M的行列式不为零,最终的余数的向量可以利用M的逆矩阵解出:


\begin{pmatrix} g \\ 0 \end{pmatrix} =
\mathbf{M}^{-1} \begin{pmatrix} a \\ b \end{pmatrix} =
(-1)^{N+1} \begin{pmatrix} m_{22} & -m_{12} \\ -m_{21} & m_{11} \end{pmatrix} \begin{pmatrix} a \\ b \end{pmatrix}

由上式可以得出g = (−1)N+1 ( m22 am12 b)。

贝祖等式的两个整数分别是s = (−1)N+1m22t = (−1)Nm12。矩阵法的效率可前文描述的辗转相除法的递归算法是相同的,每一步都有两次乘法和两次加法。

欧几里得引理和唯一分解[编辑]

贝祖等式对辗转相除法的很多应用都很重要,如证明自然数的唯一分解性质[67]假设数字L可以写成两个因数uv的乘积,即L = uv。如果另一个数wu互素的数也能整除L,那么w必须整除v,证明如下:如果uw的最大公约数是1,则根据贝祖等式存在st使

1 = su + tw

两边都乘以v

v = suv + twv = sL + twv

因为w整除等式右边,所以也应整除等式左边的v。这个结果叫做欧几里得引理[68]如果一个素数整除L那么它至少整除L的一个因数。如果一个数w互素于数列a1a2、…、an 中的每一个数,则w也一定互素于它们的乘积a1 × a2 × … × an[68]

欧几里得引理足以证明每一个自然数的素数分解是惟一的。[69]我们用反证法来证明,假设L可以分别分解成m个素数和n个素数,即:

L = p1p2pm = q1q2qn

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

线性丢番图方程[编辑]

线性丢番图方程:9x + 12y = 483的图像,它的解用蓝点表示。

丢番图方程是以亚历山大数学家丢番图的名字命名的一类方程,它的解被限制在整数范围。[70]关于整数xy的线性丢番图方程形如:[71]

ax + by = c

其中abc是已知整数。这个方程可以写成关于x同余式:

ax \equiv c \mod b

gab的最大公约数,ax + by能够被g整除。所以,c一定能够被g整除,不然方程就无解。方程两边若同时除以 \tfrac {c}{g},方程就变成了贝祖等式:

sa + tb = g

其中st可以用扩展欧几里得算法求解。[72]所以这个丢番图方程的一个解即是:


\begin{align}
x_1 = s ( \tfrac {c}{g} ) \\
y_1 = t ( \tfrac {c}{g} )
\end{align}

总体而言,丢番图方程如果有解,就一定有无数个解。[73]只需要考虑两个解 (x1, y1) 和 (x2, y2):

ax_1 + by_1 = c = ax_2 + by_2

或者可以写成:

a(x_1 - x_2) = b(y_2 - y_1)

所以相邻两个解的x之间的差是\tfrac {b}{g}y之间的差是\tfrac {a}{g}。这样,所有的解都可以表示成:


\begin{align}
x = x_1 - \tfrac{bt}{g} \\
y = y_1 + \tfrac{at}{g}
\end{align}

t取遍所有整数时,方程所有的解都可以从 (x1y1) 计算出来。如果只需要正整数解 (x > 0, y > 0) 的话,那么解的数量就可能是有限的。这种对解的限制使丢番图方程在有比普通方程组更多未知数的情况下仍然能解,[74]而在没有这种限制的普通线性方程组中,这是不可能的。

乘法逆和RSA算法[编辑]

有限域是一个支持四种运算的数的集合。这四种运算是:加、减、乘、除,它们保持原有的性质,如交换律结合律分配律。举例来说,使用同余可以让13个数字的集合 {0, 1, 2, …, 12} 构成一个有限域。在这个域中,任何数学运算(加减乘除)都归约成13的,例如 5 × 7 = 35 mod 13 = 9。对于任意素数p,都可以定义这种有限域;使用更复杂的方法,也可以对素数pm次方定义这样的有限域。有限域也叫做伽罗瓦域,缩写符号 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算法不使用域而是使用环,欧几里得辗转相除法仍然可以用来求乘法逆。辗转相除法也被应用于纠错码,例如,它可以代替Berlekamp–Massey算法解基于有限域的BCH码里德-所罗门码[78]

中国剩余定理[编辑]

辗转相除法也可以解线性丢番图方程组。[79]如在中国剩余定理中,整数可以表示成被N个互素的数mi除留下的余数:[80]


\begin{align}
x_1 &\equiv x \mod m_1 \\
x_2 &\equiv x \mod m_2 \\
\vdots & \\
x_N &\equiv x \mod m_N
\end{align}

为了从xN个余数xi中确定x的值,我们将这些式子组合成单个线性丢番图方程,其中模数M是所有模数mi的乘积,然后定义Mi如下:

 M_i = M / m_i

也就是,Mi是除了mi以外所有模数的乘积。接着是关键的一步,寻找N个数hi使:

 M_i h_i \equiv 1 \mod m_i

有了这些数hi之后,整数x可以用下式从余数xi中解出:

 x \equiv (x_1 M_1 h_1 + x_2 M_2 h_2 + \cdots + x_N M_N h_N ) \mod M

因为hiMi的乘法逆,所以可以使用辗转相除法求出(见上一节)。

连分数[编辑]

辗转相除法和连分数有着及其紧密的关系。[81]计算连分数的过程如下:


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

其中每个式子的右边最后一项都等于下一个式子的左边第一项。所以前两个式子可以组合成:

\frac{a}{b} = q_0 + \frac{1}{q_1 + \frac{r_1}{r_0}}

第三个式子可以代入分母中的r1/r0

\frac{a}{b} = q_0 + \frac{1}{q_1 + \frac{1}{q_2 + \frac{r_2}{r_1}}}

每一步中,最后一项rk/rk−1都可以用下一个式子代换,知道最后一步,结果是:

\frac{a}{b} = q_0 + \dfrac{1}{q_1 + \dfrac{1}{q_2 + \dfrac{1}{\ddots + \dfrac{1}{q_N}}}} = [ q_0; q_1, q_2, \cdots , q_N ]

上文的例子中,计算GCD(1071, 462)的过程中,商qk分别是2、3、7所以,分数 1071/462 可以写成如下连分数形式:

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

整数分解算法[编辑]

计算最大公约数是很多整数分解算法的重要步骤,[82]en:Pollard's rho algorithm,[83]秀尔算法[84]en:Dixon's factorization method[85]以及en:Lenstra elliptic curve factorization[86]而用辗转相除法括算最大公约数效率非常高。而连分数分解由于用到了连分数,所以也需要使用辗转相除法。[87]

算法效率[编辑]

用辗转相除法求 GCD(x,y) 时所需的步数。红点表示所需步骤较少(快),黄、绿、蓝点所需步骤依次增加(慢)。

辗转相除法的计算效率已经被彻底研究过了。[88]加百利·拉梅于1884年指出,一个算法的效率可以用计算所需步数乘以每步计算的开销表示。[89]用辗转相除法计算两个数的最大公约数所需的步数不会超过其中较小数的位数h的5倍。[90][91]因为每一步的计算开销通常也是h数量级的,所以辗转相除法的复杂度h2

计算步数[编辑]

计算两个自然数ab的最大公约数所需的步数可以表示为T(ab)。[92]如果ab的最大公约数是gmn是两个互素整数,使a = mgb = ng,那么:

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

这可以通过在辗转相除法的计算过程中的每一步都除以g来证明。[93]同样,当ab同时乘以w时,计算步数不变:T(ab) = T(wawb)。所以,对于数值上相近的数,如T(ab)和T(ab + 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]

最差情况[编辑]

假设用辗转相除法求自然数aba > b > 0)的最大公约数需要N步,那么满足这一条件的ab的最小值是分别是斐波那契数FN+2FN+1[94]这可以用数学归纳法证明。[95]假设N = 1,b整除a,满足这一条件的ab最小是b = 1、a = 2,正是F2F3。现在假设这一规律对M − 1有效。一个需要M步的算法的第一步是a = q0b + r0,第二步是b = q1r0 + r1。因为算法是递归的,它需要M − 1 步才能算出 GCD(br0),其中br0的最小值是 FM+1FM。所以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 < log10φ logφb = log10b,所以N ≤ 5 log10b。所以,辗转相除法不会进行超过O(h)次除法,其中h是较小数b在十进制下的位数。

平均情况[编辑]

辗转相除法的平均步骤数有三种不同的定义。第一种定义是计算已知自然数a和从0到a − 1范围内随机选取的自然数b的最大公约数所需的时间T(a):[92]

T(a) = \frac{1}{a} \sum_{0 \leq b<a} T(a, b).

但是因为T(ab)在连续整数间变化非常剧烈,所以T(a)的平均值也会显得很杂乱。[98]

为了解决这个问题,第二种定义规定τ(a)只要取遍其中所有和a互素的数即可:

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

在小于a的数中,有φ(a)个数与a互素,其中φ欧拉函数。在这个定义中,τ(a)的函数值增长地平稳很多。[99][100]

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

但是这个公式中仍然存在一个问题:ε是无穷小量。公式中的常数C等于:

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

其中γ是欧拉-马歇罗尼常数,ζ′是黎曼ζ函数的导数。[101][102]公式最左边的\frac{12}{\pi^2}\ln 2由两个独立的方法确定。[103][104]

因为第一种定义可以通过用第二种定义的求和来完成:[105]

T(a) = \frac{1}{a} \sum_{d | a} \varphi(d) \tau(d)

所以也可以由以下公式近似:[106]

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

其中Λ(d)是冯·曼戈尔特函数[107]

第三种定义Y(n)定义为从1到n间随机选取ab时计算他们的最大公约数所需的平均步骤数:[106]

Y(n) = \frac{1}{n^2} \sum_{a=1}^{n} \sum_{b=1}^{n} T(a, b) = \frac{1}{n} \sum_{a=1}^{n} T(a)

T(a)的近似公式代入,得到Y(n)的近似值:[108]

Y(n) \approx \frac{12}{\pi^2} \ln 2 \ln n + 0.06

每一步的计算开销[编辑]

在辗转相除法的每一步中,商qk和余数rk都通过rk−2rk−1求出:

rk−2 = qk rk−1 + rk.

所以每一步的计算开销主要与计算商qk的算法有关,因为余数rk可以很迅速地从rk−2rk−1qk计算出来:

rk = rk−2qk rk−1.

而计算一个h为整数的除法的算法复杂度是O(h(+1)),其中是商的位数。[109]

作为对比,辗转相除法原先的版本使用的是减法,因此效率要慢很多。进行一次除法等同于进行q次减法(其中q是商)。如果ab的比很大,计算出的商也很大,也就需要进行很多次减法。但在另一方面,计算出来的商在大多数情况下都是非常小的,除法中得出一个确定的商q的概率大约是\ln \left|\tfrac{u}{u-1}\right|。其中u = (q + 1)2[110]比如,商是1、2、3、4的可能性分别是大约41.5%、17.0%、9.3%、5.9%。因为计算机计算减法要快于除法,所以对于很大的数字,[111]基于减法的辗转相除法的性能可以比得上基于除法的算法。[112]这也被运用于二进制最大公约数算法。[113]

综合考虑算法需要的步数和每一步的计算开销,辗转相除法的随两个数字ab的平均位数成平方级的速度增长(h2)。设h0h1、…、hN−1表示计算过程中的余数r0r1、…、rN−1的位数,因为算法的步数Nh线性增长,所以算法的运算时间为:

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)

其他算法的效率[编辑]

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

计算两数ab的最大公约数有一个效率很慢的算法:将a除以从2到b之间的每一个整数以计算出它们所有的公约数,其中最大的一个即是最大公约数。在这个算法中,步骤数随b线性增长,也就是随输入数字的位数呈指数级增长。另一个很低效的算法是计算出两个数的所有素因数(见上文),最大公约数等于所有公共素因数的乘积。[7]但是整数分解算法效率极低,很多现代的加密系统甚至依靠这种低效率来防止资料被破解。[10]

除了辗转相除法之外,也有一些高效的算法存在,如二进制最大公约数算法将除法操作替换成了二进制的移位,以进一步提高用计算机运算时的效率。[114][115]但是,这种改变并没有降低算法的复杂度(仍然是O(h²)),虽然它在计算机上确实比辗转相除法快些。[116]也可以通过只检查ab的前几位数来进一步提高效率,不过效果并不明显。[117][118]二进制版的算法还可以扩展到其它进制,[119]效率最多可以提升五倍。[120]

对于超过25,000位数的大数,有一种改进使算法复杂度降低至平方级以下,[121]如Schönhage、[122][123]Stehlé、Zimmermann等人提出的算法。[124]这些算法利用2×2的矩阵(见上文)。这些亚平方级的算法复杂度通常是O(h (log h)2 (log log h))[116][125]

其他数系[编辑]

如上文所述,辗转相除法最早用来寻找两自然数的最大公约数,但其实它也可以被推广至实数,甚至是多项式二次整数赫尔维茨四元数。在这些数系中,辗转相除法甚至被用来定义一个重要概念:惟一分解,即这些数系中的数能够被惟一地分解成不能再分的元素(素数在这些数系的对应物)。惟一分解是数论中很多证明的基础。

有理数和实数[编辑]

辗转相除法可以被应用至实数,如欧几里得在几何原本第10卷中所说的那样。算法的目的是计算出实数g,使已知实数ab是它的整数倍:a = mgb = ng,其中mn整数[32]这也就找到了ab的整数关系,即找到整数st使sa + tb = 0。欧几里得使用辗转相除法来处理不可通约的长度[126][127]

实数的辗转相除法和整数的算法有两个区别。第一,余数rk是实数,虽然商qk仍然是整数。第二,算法不能保证在有限步内结束。如果能在有限步内结束,那么分数a/b是一个有理数,即:

a/b =mg/ng = m/n

于是我们可以写出它的有限连分数形式:[q0; q1, q2, …, qN]。如果算法无法结束,那么a/b无理数,可以写成无限的连分数形式:[q0; q1, q2, …]。无限连分数的一个例子是:黄金分割比φ = [1; 1, 1, …]2的算術平方根2 = [1; 2, 2, …]。通常,算法能够结束的可能性是很低的,因为对于实数ab,几乎所有a/b都是无理数。

如果算法不结束,也可以在第k步时终止计算,得到近似连分数[q0; q1, q2, …, qk]。终止时的k越大,则近似越准确。连分数m/n的分子和分母互素并满足下式:

mk = qk mk−1 + mk−2
nk = qk nk−1 + nk−2

其中递归的初始值是m−1 = n−2 = 1,m−2 = n−1 = 0mk/nka/b在分母是nk的数中最精确的有理数近似值:

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

多项式[编辑]

只含有一个变量x的多项式可以和整数一样进行加法、乘法和化简成不可再化简的多项式(也就是多项式中的“素数”)。两个多项式a(x)和b(x)的最大公约数g(x)定义为它们分解之后共有的因式的乘积,这可以用辗转相除法进行计算。[128]对于多项式的算法和整数的算法很相似,在每个步骤k,计算出满足以下递归式的商多项式qk(x)和余数多项式rk(x):

rk−2(x) = qk(x) rk−1(x) + rk(x)

其中r−2(x) = a(x),r−1(x) = b(x)。所选择的商多项式必须能使qk(x) rk−1(x)的第一项和rk−2(x)的第一项相等,这样才能保证每个余数的次数小于前一个余数 deg[rk(x)] < deg[rk−1(x)]。因为多项式的次数是非负整数,并且在每一步都减小,所以辗转相除法的计算一定能在有限步内结束。最后一个非零余数即是两个多项式a(x)和b(x)的最大公约数。[129]

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

a(x) = x4 − 4x3 + 4 x2 − 3x + 14 = (x2 − 5x + 7)(x2 + x + 2)

b(x) = x4 + 8x3 + 12x2 + 17x + 6 = (x2 + 7x + 3)(x2 + x + 2).

a(x)除以b(x)得到余数:

r_0(x) = x^3 + \frac{2}{3} x^2 + \frac{5}{3} x - \frac{2}{3}

在下一步中,b(x)除以r0(x)得到r1(x) = x2 + x + 2。最终,r0(x)除以r1(x)得到的余数为0,所以r1(x)是a(x)和b(x)的最大公约数,这和它们因式分解的结果相符合。

上文所述的很多应用也适用于多项式。[130]辗转相除法可以解多项式的线性丢番图方程和中国剩余定理,也可以用来定义多项式的连分数展开式。

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

最后,多项式的系数不必局限于整数、实数、甚至复数。这些系数可以是其他,如上文所述的有限域GF(p)。从辗转相除法得出的结论也可以直接推广至这类多项式。[128]

高斯整数[编辑]

高斯素数u + vi复平面的分布,其中u2 + v2小于500。

高斯整数是满足α = u + vi的复数,其中uv是普通整数i虚数单位(-1的平方根)。[131]通过在高斯整数中定义辗转相除法,根据上文贝祖等式可以证明高斯整数的惟一分解。[46]惟一分解性质在很多应用中都很重要,如计算勾股数或者证明费马平方和定理[131]辗转相除法用于这些应用很方便,但并非必不可少,一些定理也可以由其他方式证明。

对于两个高斯整数α和β的辗转相除法和普通整数只有两个区别。像整数一样,算法的第k步计算出商qk和余数rk

rk = rk−2qk rk−1

其中rk−2 = α,rk−1 = β,每个余数都严格地小于前一个余数,|rk| < |rk−1|。第一个区别即是:商和余数都是高斯整数,也就是复数,所以商qk的实部和虚部都要取近似值。第二个区别就是需要定义复数比较大小的方法。所以我们定义一个范数函数f(u + vi) = u2 + v2,以将高斯整数u + vi转换成普通整数来比较大小。在每个步骤k中,余数的范数f(rk)必须小于前一个余数的范数f(rk−1)。因为范数是非负整数并且在每一步都减小,所以辗转相除法在有限步内一定能结束。最后一个非零余数即是α和β的最大公约数,即能同时整除α和β的整数中范数最大的一个。

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

欧几里得整环[编辑]

如果一个支持两种二元运算(+ 和 ·)的元素的集合形成一个交换环并且可以使用辗转相除法求最大公约数,那么这个集合叫做欧几里得整环[132][133]这两个二元运算不必是平常算数中的加法和乘法,它们可以是更广泛的概念,如幺半群中的运算。但是这些运算仍然需要遵守交换律结合律分配律

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

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

欧几里得整环的惟一分解性质在很多场合都非常有用。例如,高斯整数的惟一分解性质可以方便地导出勾股数的公式,或者证明费马平方和定理[131]惟一分解性质也是加百利·拉梅于1847年基于约瑟夫·刘维尔的建议发表的证明费马最后定理的尝试中的关键部分。[134]拉梅的尝试需要形如x + ωy的数的惟一分解性质,其中xy是整数,ω = e2iπ/n是1的n次方根,即ωn = 1。虽然这对于某些n成立(如n=3时的艾森斯坦整数),但在其他情况下并非总是正确的。惟一分解性质在分圆域的失效使恩斯特·库默尔发明了理想数的概念,随后理查德·戴德金创造了理想的概念。[來源請求]

二次整数的惟一分解[编辑]

艾森斯坦素数u + vω在复平面的分布(范数小于500,ω等于1的立方根)。

二次整数环对于解释欧几里得整环很有帮助。二次整数是高斯整数的推广,高斯整数中的虚数单位i被替换成一个复数ω。二次整数的形式是u + vω,其中uv是整数,ω有两种形式,取决于参数D。如果D不等于四的倍数加一,那么:

\omega = \sqrt{D}

如果D等于四的倍数加一,那么:

\omega = \frac{1 + \sqrt{D}}{2}

如果二次整数环有像上文用来比较高斯整数的那样的范数函数,那么它就是规范欧几里德整环。只有当D = −11, −7, −3, −2, −1, 2, 3, 5, 6, 7, 11, 13, 17, 19, 21, 29, 33, 37, 41, 57或73时,二次整数环才是规范欧几里德整环[25]D = −1和−3时的二次整数分别叫作高斯整数艾森斯坦整数

但如果范数函数f可以是任何欧几里得函数,那么使二次整数环是欧几里得整环的D的可能值到目前为止还不确定。[135]是欧几里得整环但不是规范欧几里德整环的第一个例子(D=69)发表于1994年[135]1973年,温伯格证明,D>0时的二次整数环是欧几里得整环的条件只需要他是一个主理想环,这使广义黎曼猜想能够成立。[136]

非交换环[编辑]

辗转相除法也可以应用至非交换环,如赫尔维茨四元数[137]αβ表示这样一个环中的两个元素。他们有右公约数δ如果α = ξδβ = ηδξη是环中的元素)。同样,他们有左公约数δ如果α = δξβ = δηξη是环中的元素)。因为乘法不符合交换律,也就有两个版本的辗转相除法,一个计算右公约数,一个计算左公约数。例如对于右公约数,辗转相除法求最大公约数的第一步可以写成:

ρ0 = αψ0β = (ξψ0η)δ

其中ψ0是商,ρ0是余数。对于左公约数,第一步过程是:

ρ0 = αβψ0 = δ(ξηψ0)

不管是哪一种,这个过程都会重复到最大左公约数或者左公约数计算出,想在欧几里得整环中一样,ρ0的“大小”一定小于β,并且ρ0的可能值只有有限种,这样才能保证算法能够结束。

由辗转相除法得出的大多数结果都适用于非交换环。例如,贝祖等式表明最大右公约数可以表示成α的倍数和β的倍数的和,即,存在σ和τ使:

Γ = σα + τβ

对于最大左公约数,等式如下:

Γ = ασ + βτ

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

推广至其他数学结构[编辑]

辗转相除法可以推广至纽结理论[138]

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

rk = rk−2qk rk−1

其中每一个余数都比前一个余数小,|rk| < |rk−1|。第二,余数的大小有下限,如|rk| ≥ 0。第三,小于|rk|的数的数量是有限的。辗转相除法推广至其他数学结构,如tangles[139]超限序数[140]时仍保持这种性质。

辗转相除法的一个重要推广是代数几何格罗布纳基的概念。像前文所述,ab的最大公约数g 是它们的理想的生成元素。也就是说,对任何整数st,存在另一个整数m使:

sa + tb = mg.

虽然这对一元多项式也成立,但是对多元多项式就不成立了。[141]在多元多项式的情况下,生成元素的有限集合g1g2……可以定义如下:

sa + tb = Σk mkgk

其中stmk是多元多项式。[142]任何这样的多元多项式f可以表示成生成多项式的和加上惟一的余数多项式r, 通常叫做多项式f一般形式

f = r + Σk qkgk

虽然商多项式qk可能不惟一。[143]这些生成多项式的集合就叫做格罗布纳基。[144]

参考资料[编辑]

  1. ^ 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.
  2. ^ Stark, p. 16.
  3. ^ Stark, p. 21.
  4. ^ LeVeque, p. 32.
  5. ^ Leveque, p. 31.
  6. ^ Grossman JW. Discrete Mathematics. New York: Macmillan. 1990. 213. ISBN 0-02-348331-8. 
  7. ^ 7.0 7.1 Schroeder, pp. 21–22.
  8. ^ Schroeder, p. 19.
  9. ^ Ogilvy CS, Anderson JT. Excursions in number theory. New York: Oxford University Press. 1966: 27–29. LCCN 66-14484. 
  10. ^ 10.0 10.1 Schroeder, pp. 216–219.
  11. ^ 11.0 11.1 Leveque, p. 33.
  12. ^ Stark, p. 25.
  13. ^ Ore, pp. 47–48.
  14. ^ 高德纳. The Art of Computer Programming(计算机程序设计艺术), Volume 1: Fundamental Algorithms 3rd. Addison-Wesley. 1997. ISBN 0-201-89683-4.  (Section 1.2.1: Mathematical Induction, pp. 11–21.)
  15. ^ Rosen, pp. 18–21.
  16. ^ Rosen, pp. 21–24.
  17. ^ Anderson JA. Discrete Mathematics with Combinatorics. Upper Saddle River, NJ: Prentice Hall. 2001: 165–223. ISBN 0-13-086998-8. 
  18. ^ Rosen, p. 492.
  19. ^ Anderson JA. Discrete Mathematics with Combinatorics. Upper Saddle River, NJ: Prentice Hall. 2001: 109–119. ISBN 0-13-086998-8. 
  20. ^ 20.0 20.1 Stark, p. 18.
  21. ^ 21.0 21.1 Stark, pp. 16–20.
  22. ^ 高德纳, p. 320.
  23. ^ Lovász L, Pelikán J, Vesztergombi K. Discrete Mathematics: Elementary and Beyond. New York: Springer-Verlag. 2003: 100–101. ISBN 0-387-95584-4. 
  24. ^ Kimberling C. A Visual Euclidean Algorithm. Mathematics Teacher. 1983, 76: 108–109. 
  25. ^ 25.0 25.1 Cohn, pp. 104–110.
  26. ^ 高德纳, pp. 319–320.
  27. ^ 高德纳, pp. 318–319.
  28. ^ Stillwell, p. 14.
  29. ^ 29.0 29.1 Ore, p. 43.
  30. ^ 30.0 30.1 Stewart BM. Theory of Numbers 2nd. New York: Macmillan. 1964: 43–44. LCCN 64-10964. 
  31. ^ 31.0 31.1 高德纳, p. 318.
  32. ^ 32.0 32.1 Weil A. Number Theory. Boston: Birkhäuser. 1983: 4–6. ISBN 0-8176-3141-0. 
  33. ^ Jones A. Greek mathematics to AD 300//Companion encyclopedia of the history and philosophy of the mathematical sciences. New York: Routledge. 1994: 46–48. ISBN 0-415-09238-8. 
  34. ^ van der Waerden BL. Science Awakening. translated by Arnold Dresden. Groningen: P. Noordhoff Ltd. 1954: 114–115. 
  35. ^ von Fritz K. The Discovery of Incommensurability by Hippasus of Metapontum. Ann. Math. 1945, 46: 242–264. doi:10.2307/1969021. 
  36. ^ Heath TL. Mathematics in Aristotle. Oxford Press. 1949: 80–83. 
  37. ^ Fowler DH. The Mathematics of Plato's Academy: A New Reconstruction. Oxford: Oxford University Press. 1987: 31–66. ISBN 0-19-853912-6. 
  38. ^ Becker O. Eudoxus-Studien I. Eine voreuklidische Proportionslehre und ihre Spuren bei Aristoteles und Euklid. Quellen und Studien zur Geschichte der Mathematik B. 1933, 2: 311–333. 
  39. ^ 39.0 39.1 Stillwell, p. 31.
  40. ^ Rosen, pp. 86–87.
  41. ^ Tattersall, p. 70.
  42. ^ Wikisource link to 九章算术. 维基文库 (中文). "可半者半之;不可半者,副置分母、子之數,以少減多,更相減損,求其等也。以等數約之。" 
  43. ^ Ore, pp. 247–248.
  44. ^ Tattersall, p. 70.
  45. ^ Tattersall, pp. 72–76.
  46. ^ 46.0 46.1 Gauss CF. Theoria residuorum biquadraticorum. Comm. Soc. Reg. Sci. Gött. Rec. 1832, 4.  See also Werke, 2:67–148.
  47. ^ Stillwell, pp. 31–32.
  48. ^ 狄利克雷, pp. 29–31.
  49. ^ Dedekind R. Supplement XI//PGL 狄利克雷 (编). Vorlesungen über Zahlentheorie. 1894. 
  50. ^ Stillwell J. Elements of Number Theory. New York: Springer-Verlag. 2003: 41–42. ISBN 0-387-95587-9. 
  51. ^ Sturm C. Mémoire sur la résolution des équations numériques. Bull. des sciences de Férussac. 1829, 11: 419–422. 
  52. ^ 埃里克·韦斯坦因, Integer Relation at MathWorld
  53. ^ Peterson I. Jazzing Up Euclid's Algorithm. ScienceNews. 12 August 2002. 
  54. ^ Cipra BA. The Best of the 20th Century: Editors Name Top 10 Algorithms. SIAM News (Society for Industrial and Applied Mathematics). 16 May 2000, 33 (4). 
  55. ^ Cole AJ, Davie AJT. A game based on the Euclidean algorithm and a winning strategy for it. Math. Gaz. 1969, 53: 354–357. doi:10.2307/3612461. 
  56. ^ Spitznagel EL. Properties of a game based on Euclid's algorithm. Math. Mag. 1973, 46: 87–92. 
  57. ^ Rosen, p. 95.
  58. ^ Roberts J. Elementary Number Theory: A Problem Oriented Approach. Cambridge, MA: MIT Press. 1977: 1–8. ISBN 0-262-68028-9. 
  59. ^ Jones GA, Jones JM. Bezout's Identity//Elementary Number Theory. New York: Springer-Verlag. 1998: 7–11. 
  60. ^ Rosen, p. 81.
  61. ^ Cohn, p. 104.
  62. ^ Rosen, p. 91.
  63. ^ Schroeder, p. 23.
  64. ^ Rosen, pp. 90–93.
  65. ^ 65.0 65.1 Koshy T. Elementary Number Theory with Applications. Burlington, MA: Harcourt/Academic Press. 2002: 167–169. ISBN 0-12-421171-2. 
  66. ^ Bach E, Shallit J. Algorithmic number theory. Cambridge, MA: MIT Press. 1996: 70–73. ISBN 0-262-02405-5. 
  67. ^ Stark, pp. 26–36.
  68. ^ 68.0 68.1 Ore, p. 44.
  69. ^ Stark, pp. 281–292.
  70. ^ Rosen, pp. 119–125.
  71. ^ Schroeder, pp. 106–107.
  72. ^ Schroeder, pp. 108–109.
  73. ^ Rosen, pp. 120–121.
  74. ^ Stark, p. 47.
  75. ^ Schroeder, pp. 107–109.
  76. ^ Stillwell, pp. 186–187.
  77. ^ Schroeder, p. 134.
  78. ^ "Error correction coding: mathematical methods and algorithms", page 266, Todd K. Moon, John Wiley and Sons, 2005, ISBN 0-471-64800-0
  79. ^ Rosen, pp. 143–170.
  80. ^ Schroeder, pp. 194–195.
  81. ^ Vinogradov IM. Elements of Number Theory. New York: Dover. 1954: 3–13. 
  82. ^ Crandall R, Pomerance C. Prime Numbers: A Computational Perspective 1st. New York: Springer-Verlag. 2001: 225–349. ISBN 0-387-94777-9. 
  83. ^ 高德纳, pp. 369–371.
  84. ^ Shor PW. Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer. SIAM J. Sci. Statist. Comput. 1997, 26: 1484. 
  85. ^ Dixon JD. Asymptotically fast factorization of integers. Math. Comput. 1981, 36: 255–260. doi:10.2307/2007743. 
  86. ^ Lenstra Jr. HW. Factoring integers with elliptic curves. Annals of Mathematics. 1987, 126: 649–673. doi:10.2307/1971363. 
  87. ^ 高德纳, pp. 380–384.
  88. ^ 高德纳, pp. 339–364.
  89. ^ 加百利·拉梅. Note sur la limite du nombre des divisions dans la recherche du plus grand commun diviseur entre deux nombres entiers. Comptes Rendus Acad. Sci. 1844, 19: 867–870. 
  90. ^ Grossman H. On the Number of Divisions in Finding a G.C.D.. The American Mathematical Monthly. 1924, 31: 443. doi:10.2307/2298146. 
  91. ^ Honsberger R. Mathematical Gems II. The Mathematical Association of America. 1976: 54–57. ISBN 0-88385-302-7. 
  92. ^ 92.0 92.1 92.2 高德纳, p. 344.
  93. ^ Ore, p. 45.
  94. ^ 94.0 94.1 高德纳, p. 343.
  95. ^ Mollin, p. 21.
  96. ^ LeVeque, p. 35.
  97. ^ Mollin, pp. 21–22.
  98. ^ 高德纳, p. 353.
  99. ^ 高德纳, p. 357.
  100. ^ Tonkov T. On the average length of finite continued fractions. Acta arithmetica. 1974, 26: 47–57. 
  101. ^ Porter JW. On a Theorem of Heilbronn. Mathematika. 1975, 22: 20–28. 
  102. ^ 高德纳 DE. Evaluation of Porter's Constant. Computers and Mathematics with Applications. 1976, 2: 137–139. doi:10.1016/0898-1221(76)90025-0. 
  103. ^ Dixon JD. The Number of Steps in the Euclidean Algorithm. J. Number Theory. 1970, 2: 414–422. doi:10.1016/0022-314X(70)90044-2. 
  104. ^ Heilbronn HA. On the Average Length of a Class of Finite Continued Fractions//Paul Turán (编). Number Theory and Analysis. New York: Plenum. 1969: 87–96. LCCN 68-8991. 
  105. ^ 高德纳, p. 354.
  106. ^ 106.0 106.1 Norton GH. On the Asymptotic Analysis of the Euclidean Algorithm. Journal of Symbolic Computation. 1990, 10: 53–58. doi:10.1016/S0747-7171(08)80036-3. 
  107. ^ 高德纳, p. 355.
  108. ^ 高德纳, p. 356.
  109. ^ 高德纳, pp. 257–261.
  110. ^ 高德纳, p. 352.
  111. ^ Wagon S. Mathematica in Action. New York: Springer-Verlag. 1999: 335–336. ISBN 0-387-98252-3. 
  112. ^ Cohen, p. 14.
  113. ^ Cohen, pp. 14–15, 17–18.
  114. ^ 高德纳, pp. 321–323.
  115. ^ Stein J. Computational problems associated with Racah algebra. Journal of Computational Physics. 1967, 1: 397–405. doi:10.1016/0021-9991(67)90047-2. 
  116. ^ 116.0 116.1 Crandall R, Pomerance C. Prime Numbers: A Computational Perspective 1st. New York: Springer-Verlag. 2001: 77–79, 81–85, 425–431. ISBN 0-387-94777-9. 
  117. ^ 高德纳, p. 328.
  118. ^ Lehmer DH. Euclid's Algorithm for Large Numbers. The American Mathematical Monthly. 1938, 45: 227–233. doi:10.2307/2302607. 
  119. ^ Sorenson J. Two fast GCD algorithms. J. Algorithms. 1994, 16: 110–144. doi:10.1006/jagm.1994.1006. 
  120. ^ Weber K. The accelerated GCD algorithm. ACM Trans. Math. Soft. 1995, 21: 111–122. doi:10.1145/200979.201042. 
  121. ^ Aho A, Hopcroft J, Ullman J. The Design and Analysis of Computer Algorithms. New York: Addison–Wesley. 1974: 300–310. 
  122. ^ Schönhage A. Schnelle Berechnung von Kettenbruchentwicklungen. Acta Informatica. 1971, 1: 139–144. doi:10.1007/BF00289520. 
  123. ^ Cesari G. Parallel implementation of Schönhage's integer GCD algorithm//In G. Buhler. Algorithmic Number Theory: Proc. ANTS-III, Portland, OR. New York: Springer-Verlag. 1998: 64–76.  Volume 1423 in Lecture notes in Computer Science.
  124. ^ Stehlé D, Zimmermann P. Gal’s accurate tables method revisited//Proceedings of the 17th IEEE Symposium on Computer Arithmetic (ARITH-17). Los Alamitos, CA: IEEE Computer Society Press. 2005. 
  125. ^ Möller N. On Schönhage's algorithm and subquadratic integer gcd computation. Mathematics of Computation. 2008, 77: 589–607. doi:10.1090/S0025-5718-07-02017-0. 
  126. ^ Boyer CB, Merzbach UC. A History of Mathematics 2nd. New York: Wiley. 1991: 116–117. ISBN 0-471-54397-7. 
  127. ^ Cajori F. A History of Mathematics. New York: Macmillan. 1894. 70. 
  128. ^ 128.0 128.1 Lang S. Algebra 2nd. Menlo Park, CA: Addison–Wesley. 1984: 190–194. ISBN 0-201-05487-6. 
  129. ^ Cox, pp. 37–46.
  130. ^ Schroeder, pp. 254–259.
  131. ^ 131.0 131.1 131.2 Stillwell J. Elements of Number Theory. New York: Springer-Verlag. 2003: 101–116. ISBN 0-387-95587-9. 
  132. ^ Stark, p. 290.
  133. ^ Cohn, pp. 104–105.
  134. ^ Lamé G. Mémoire sur la résolution, en nombres complexes, de l'équation An + Bn + Cn = 0. J. Math. Pures Appl. 1847, 12: 172–184. 
  135. ^ 135.0 135.1 Clark DA. A quadratic field which is Euclidean but not norm-Euclidean. Manuscripta mathematica. 1994, 83: 327–330. doi:10.1007/BF02567617. 
  136. ^ Weinberger P. On Euclidean rings of algebraic integers. Proc. Sympos. Pure Math.: 321–332. 
  137. ^ Stillwell J. Elements of Number Theory. New York: Springer-Verlag. 2003: 151–152. ISBN 0-387-95587-9. 
  138. ^ Yamada Y. Generalized rational blow-down, torus knots, and Euclidean algorithm. arXiv:0708.2316v1. 2007. 
  139. ^ Conway, John Horton. An enumeration of knots and links, and some of their algebraic properties//Computational Problems in Abstract Algebra (Proc. Conf., Oxford, 1967). Pergamon. 1970: 329–358. 
  140. ^ Jategaonkar AV. Rings with transfinite left division algorithm. Bull. Amer. Math. Soc. 1969, 75: 559–561. doi:10.1090/S0002-9904-1969-12242-1. 
  141. ^ Cox, p. 65.
  142. ^ Cox, pp. 73–79.
  143. ^ Cox, pp. 79–86.
  144. ^ Cox, p. 74.

书籍[编辑]

外部链接[编辑]