辗转相除法 在数学中，辗转相除法，又称欧几里得算法（），是求最大公约数的算法。辗转相除法首次出现于欧几里得的《几何原本》（第VII卷，命题i和ii）中，而在中国则可以追溯至东汉出现的《九章算术》。 两个整数的最大公约数是能够同时整除它们的最大的正整数。辗转相除法基于如下原理：两个整数的最大公约数等于其中较小的数和两数相除余数的最大公约数。例如，欲求252和105的最大公约数（formula_1）；因为formula_2，所以这个最大公约数也是42与105的最大公约数(formula_3)。在这个过程中，较大的数缩小了，所以继续进行同样的计算可以不断缩小这两个数直至余数为零。这时，所剩下的还没有变成零的数就是两数的最大公约数。由辗转相除法也可以推出，两数的最大公约数可以用两数的整数倍相加来表示，如formula_4。这个重要的结论叫做贝祖定理。 辗转相除法最早出现在欧几里得的《几何原本》中（大约公元前300年），所以它是现行的算法中历史最悠久的。这个算法原先只用来处理自然数和几何长度（相当于正实数），但在19世纪，辗转相除法被推广至其他类型的数学物件，如高斯整数和一元多项式。由此，引申出欧几里得整环等等的一些现代抽象代数概念。后来，辗转相除法又扩展至其他数学领域，如纽结理论和多元多项式。 辗转相除法有很多应用，它甚至可以用来生成全世界不同文化中的传统音乐节奏。在现代密码学方面，它是RSA算法（一种在电子商务中广泛使用的公钥加密算法）的重要部分。它还被用来解丢番图方程，比如寻找满足中国剩余定理的数，或者求有限域中元素的逆。辗转相除法还可以用来构造连分数，在施图姆定理和一些整数分解算法中也有应用。辗转相除法是现代数论中的基本工具。 辗转相除法处理大数时非常高效，如果用除法而不是减法实现，它需要的步骤不会超过较小数的位数（十进制下）的五倍。拉梅于1844年证明了这点，同时这也标志著计算复杂性理论的开端。 背景. 最大公约数. 欧几里得的辗转相除法计算的是两个自然数formula_5和formula_6的最大公约数formula_7，意思是能够同时整除formula_5和formula_6的自然数中最大的一个。两个数的最大公约数通常写成formula_10，或者简写成formula_11，但是第二种写法也被使用在其他数学概念，如二维向量的坐标。 如果formula_12，则称formula_5和formula_6互素。"a"和"b"是否互素和它们是否素数无关。如，6和35都不是素数，因为它们都可以分解为多于一个素因数的乘积：6 = 2 × 3，35 = 5 × 7。但是，6和35互素，因为除了1以外没有自然数同时整除6和35。 令formula_15。由于formula_5和formula_6都是"formula_7"的整数倍，所以可以写成formula_19，并且不存在更大的整数formula_20使等式成立。为了使"formula_7"尽可能大，就要使formula_5和formula_6中所有公约数都提取出来归入"formula_7"中，所以自然数formula_25和formula_26一定互素，并且formula_5和formula_6的最大公约数"formula_7"可以被formula_5和formula_6的所有其他公因数formula_32整除。 我们可以用右图来解释最大公约数的概念：设一个长方形的边长为formula_5和formula_6。因为formula_5和formula_6的任何公约数"formula_32"都可以整除formula_5和formula_6，所以长方形的边都可以等分为长度为"formula_32"的线段，也就是长方形可以被边长为"formula_32"的正方形正好填满。而最大公约数"formula_7"是所有可能的"formula_32"中最大的一个。例如，一个24 × 60的长方形区域可以分成1 × 1、2 × 2、3 × 3、6 × 6或12 × 12的正方形网格。也就是说，12是24和60的最大公约数。 formula_5和formula_6的最大公约数是两数共有的素因数的乘积。例如，462可以分解成2 × 3 × 7 × 11；1071可以分解成3 × 3 × 7 × 17。462和1071的最大公约数等于它们共有的素因数的乘积3 × 7 = 21。如果两数没有公共的素因数，那么它们的最大公约数是1，也即这两个数互素。辗转相除法的优点就在于它能以有系统的方式求出两数的最大公约数，而无需分别对它们作因式分解。大数的素因数分解被认为是一个困难的问题，即使是现代的计算机也非常难于处理，所以许多加密系统的原理都是建基于此。 在数学中，尤其是抽象代数的环论中，最大公约数有一个更加巧妙的定义：formula_5和formula_6的最大公约数"formula_7"是formula_5和formula_6的线性和中的最小正整数，即所有形如formula_51（其中formula_52和formula_53是整数）的数中的最小正整数。可以证明，所有formula_51都是"formula_7"的整数倍（formula_56，其中formula_25是整数）。用现代数学语言来说，formula_5和formula_6生成的理想即是由"formula_7"生成的主理想。最大公约数的这个定义和其他定义的等价性将在下面描述。 三个数的最大公约数的定义和两个数的相同，即是它们共有的素因数的积，它们或者也可以按下式计算： formula_61 所以，欧几里得的辗转相除法实际可以计算任意多整数的最大公约数。 归纳、递归和无穷递降. 下文的论证会用到三种相关的数学方法，分别是数学归纳法、递归和无穷递降。数学归纳法经常用来证明某个定理对所有自然数成立：首先证明定理对一个特定的数formula_62成立（通常是1）；然后证明如果定理对自然数formula_26成立的话，那么它对自然数formula_64成立。这样，便可证明定理对所有大于formula_62的自然数也成立。递归是将相关的数组成一个数列（formula_66），当中除初始项外，其中每一项都用前一项或前几项表示。如斐波那契数列就是递归的，每一项formula_67都等于formula_68（formula_69）。辗转相除法中的一些等式也是递归的。最后，无穷递降是用方程的一个自然数解导出比它小的自然数解。但是，这种转化不能永远进行下去，因为只有有限个小于原来的自然数解的自然数。所以，要么方程无解，不然在有限步内必然能得出最小的自然数解。在下文会用到此法来证明辗转相除法一定会在有限步内结束。 算法描述. 计算过程. 辗转相除法是一种递归算法，每一步计算的输出值就是下一步计算时的输入值。设formula_70表示步骤数（从0开始计数），算法的计算过程如下。 每一步的输入是都是前两次计算的非负余数formula_71和formula_72。因为每一步计算出的余数都在不断减小，所以，formula_71小于formula_72。在第"formula_70"步中，算法计算出满足以下等式的商formula_76和余数formula_77： formula_78 其中formula_79。也就是formula_72要不断减去formula_71直到比formula_71小。 为求简明，以下只说明如何求两个非负整数formula_5和formula_6的最大公约数（负数的情况是简单的）。在第一步计算时（formula_85），设formula_86和formula_87分别等于formula_5和formula_6，第2步（此时formula_90）时计算formula_87（即formula_6）和formula_93（第一步计算产生的余数）相除产生的商和余数，以此类推。整个算法可以用如下等式表示： 如果有a，算法的第一步实际上会把两个数字交换，因为这时"formula_5"除以"formula_6"所得的商formula_96会等于0，余数formula_93则等于formula_5。然后，算法的第二步便是把"formula_6"除以"formula_5"，再计算所得之商和余数。所以，对于formula_101总有formula_102，即运算的每一步中得出的余数一定小于上一步计算的余数。 由于每一步的余数都在减小并且不为负数，必然存在第formula_26步时formula_104等于0，使算法终止，formula_105就是"formula_5"和"formula_6"的最大公约数。其中"formula_26"不可能无穷大，因为在formula_93和0之间只有有限个自然数。 正确性的证明. 辗转相除法的正确性可以分成两步来证明。在第一步，我们会证明算法的最终结果formula_105同时整除"formula_5"和"formula_6"。因为它是一个公约数，所以必然小于或者等于最大公约数formula_7。在第二步，我们证明"formula_7"能整除formula_105。所以"formula_7"一定小于或等于formula_105。两个不等式只在formula_118时同时成立。 具体证明如下： 举例. 例如，计算formula_156和formula_157的最大公约数的过程如下：从1071中不断减去462直到小于462（可以减2次，即商formula_158），余数是147： formula_159 然后从462中不断减去147直到小于147（可以减3次，即formula_160），余数是21： formula_161 再从147中不断减去21直到小于21（可以减7次，即formula_162），没有余数： formula_163 此时，余数是0，所以1071和462的最大公约数是21，这和用素因数分解得出的结果相同（见上文）用表格表示如下： 图形演示. 辗转相除法的计算过程可以用图形演示。假设我们要在formula_164的矩形地面上铺正方形瓷砖，并且正好铺满，其中formula_5大于formula_6。我们先尝试用formula_167的瓷砖，但是留下了formula_168的部分，其中formula_169的正方形瓷砖铺，又留下了formula_170的部分，然后再使用formula_171的正方形铺……直到全部铺满为止，即到某步时正方形刚好覆盖剩余的面积为止。此时用到的最小的正方形的边长就是原来矩形的两条边长的最大公约数。在图中，最小的正方形面积是21×21（红色），而原先的矩形（绿色）边长是1071×462，所以21是1071和462的最大公约数。 计算商和余数. 在每个步骤formula_70中，辗转相除法都需要计算两个数formula_71和formula_72的商formula_76和余数formula_77： formula_78 其中formula_178。除法的算法保证这样的商和余数总是存在。自然数的除法算法还指出这样的商和余数是惟一的，但这对辗转相除法而言并非必要。 在欧几里得最初的描述中，商和余数是通过连续的减法来计算的，即从formula_72中不断减去formula_71直到小于formula_71。一个更高效的做法是使用整数除法和模除来计算商和余数： formula_182 计算机实现. 辗转相除法可用伪代码表示，比如除法版本可以写成 function gcd(a, b) while b ≠ 0 t ← b b ← a mod b a ← t return a C++版本： int gcd(int m, int n) { int t = 1; while(t != 0) { t = m % n; m = n; n = t; return m; Rust版本： fn gcd(x: isize, y: isize) -> Option { 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()) Python 3版本： def gcd(a, b): while b != 0: t = a % b a = b b = t return a 在第formula_70次循环开始时，变量formula_6的值是前一次运算的余数formula_71，变量formula_5的值是再前一次运算的余数formula_72。步骤formula_188的作用等同于递归式formula_182。变量formula_190的功能是在下一个余数formula_77计算过程中临时性地保存formula_71的值。在一次循环结束时，变量"formula_6"的值是前一次运算的余数"formula_77"，变量"formula_5"的值是再前一次运算的余数formula_71。 在欧几里得定义的减法版本，取余运算被减法替换。 function gcd(a, b) if a = 0 return b while b ≠ 0 if a > b a ← a − b else b ← b − a return a 变量"formula_5"和"formula_6"的值分别是前两次的余数formula_71和formula_72。假定第"formula_70"次循环开始时"formula_5"大于"formula_6"，那么"formula_5"等于formula_72，因为formula_206。在循环过程中，"formula_5"重复减去"formula_6"直到比"formula_6"小，此时"formula_5"就是下一个余数"formula_77"；然后"formula_6"重复减去"formula_5"直到比"formula_5"小，此时"formula_6"就是下一个余数formula_216；重复执行直到formula_217。 以下是递归版本： function gcd(a, b) if b = 0 return a else return gcd(b, a mod b) C++递归版本如下： int gcd(int n,int m) return m == 0 ? n : gcd(m, n % m); Rust递归版本： fn gcd(x: isize, y: isize) -> Option { match (x,y) { (0, 0) => None, (a, 0) => Some(a.abs()), _ => gcd(y, x % y), Java版本： public class MethodOfSuccessiveDivision { public static void main(String[] args) { System.out.println(gcd(1071, 462)); public static int gcd(int a, int b){ if(b == 0){ return a; }else{ return gcd(b, a % b ); Python 3版本： def gcd(a, b): return a if b == 0 else gcd(b, a % b) 例如formula_218的计算过程是：函数的第一次调用计算formula_219；下一次调用计算formula_220，在接下来是formula_221。 使用绝对值最小的余数. 在另一个版本的算法中，每一步还要把取余运算时计算出的商增加一后再重新计算余数（此时计算出的余数应该是负的），然后取两个余数的绝对值较小的数作为下一步运算时使用的余数。取余运算后，设"formula_77"是计算出的余数（此时为正），formula_223是计算出的商： formula_78 即假设formula_225。然后使用以下式子计算出一个负的余数formula_226： formula_227 如果formula_228，那么用"formula_226"替换"formula_77"进行下一次运算。如利奥波德·克罗内克所指出的，这个版本需要的运算步骤是欧几里得算法的所有版本中最少的。 历史发展. 辗转相除法是目前仍然在使用的历史最悠久的算法之一。它首次出现于《几何原本》（卷7命题1–2、卷10命题2–3）（大约公元前300年）。在卷7中用于整数，在卷10中用于线段的长度（以现代的观点看，线段的长度可视为正实数，也就是说辗转相除法实际可用于实数上，但是当时未有实数的概念）。卷10中出现的算法是几何的，两段线段"a"和"b"的最大公约数是"a"和"b"的公度中的最大值。 这个算法可能并非欧几里得发明，因为他也有将先前其他数学家的一些成果编进他的《几何原本》。数学家、历史学家范德瓦尔登认为卷7的内容可能来自毕达哥拉斯学院出身的数学家写的关于数论的教科书。辗转相除法在当时很可能已为尤得塞斯（大约公元前375年）所知 ，甚至可能更早之前就已经存在，因为欧几里得和亚里士多德的著作中都出现了-- 一词（意为“辗转相减”）。 几个世纪之后，辗转相除法又分别被中国人和印度人独立发现，主要用来解天文学中用到的丢番图方程以及制定准确的历法。5世纪末，印度数学家、天文学家阿里亚哈塔曾称辗转相除法为“粉碎机”，这可能是因为它在解丢番图方程时很有效。在中国，《九章算术》中提到了一种类似辗转相减法的“更相减损术”。《孙子算经》中则出现了中国剩余定理的一个特例，但是直到1247年秦九韶才于其《数学九章》中解答了该定理的一般情况，当中用到了他发明的大衍求一术。此法的其中一部分实际上便是辗转相除的原理，秦九韶在书中对此有明确表述。在欧洲，辗转相除法首次出现于的著作《愉悦讨喜的问题》（"-- "）的第二版在欧洲，辗转相除法被用于丢番图方程和构建连分数。后来，英国数学家在其著作中收编了扩展欧几里得算法，作为一个有效计算连分数的方法。他将此法的来源归名于。 19世纪，辗转相除法促成了新数系的建立，如高斯整数和艾森斯坦整数。1815年，高斯用辗转相除法证明高斯整数的分解是惟一的，尽管他的研究到了1832年才首度发表。高斯在他的《算数研究》（出版于1801年）中实际上也有援引这个算法，但仅是以连分数方法的形式叙述。约翰·狄利克雷是第一个将辗转相除法作为数论的基础的数学家。#重定向 -{H|zh-cn:重定向;zh-tw:重新导向;}-狄利克雷提出，数论中的很多结论，如分解的惟一性，在任何使辗转相除法适用的数系中均有效。狄利克雷的数论讲义后来经理查德·戴德金编辑和推广，戴德金也有以辗转相除法来研究代数整数。比如，他是第一个用高斯整数的分解惟一性证明费马平方和定理的数学家。戴德金还率先定义了欧几里得整环的概念。19世纪末，戴德金所定义的理想概念使得数论的重心不必建基于辗转相除法，从而促进了理论的发展。 辗转相除法的其他应用发展于19世纪。1829年，施图姆将辗转相除法用于施图姆序列（用于确定多项式的不同实根的个数的方法）。 辗转相除法是历史上第一个，即寻找两个可通约实数的整数关系的算法。近年来，出现了一些新颖的整数关系算法，如和福尔卡德于1979年发表的弗格森-福尔卡德算法（Ferguson–Forcade algorithm） 、以及与它相关的、HJLS算法以及PSLQ算法。 1969年，科尔（Cole）和戴维（Davie）基于辗转相除法创造了一种二人游戏，叫做「欧几里得游戏」。这个游戏有最优策略。游戏开始于两列分别为"a"和"b"个棋子组成的序列，玩家轮流从较长一列中取走较短一列棋子数量的"m"倍的棋子。如果两列棋子"p"和"q"分别由"x"和"y"个棋子组成，其中"x"大于"y"，那么玩家可以将序列"p"的棋子数量减少为自然数"x" − "my"。最后率先将一列棋子清空的玩家胜出。 数学上的应用. 贝祖等式. 贝祖等式说明，两个数formula_5和formula_6的最大公约数formula_7可以表示为formula_5和formula_6的线性和。也就是说，存在整数formula_236和formula_190使formula_238。 整数formula_236和formula_190可以从辗转相除法算出的商formula_241计算出。 从辗转相除法的最后一步开始，"formula_7"可以表示成前一步的商formula_243和前两步的余数formula_244和formula_245： formula_246 而前两步的余数又分别可以表示成它们前两步的余数和商： formula_247 formula_248 将这两行式子先后代入第一个式子，可以将formula_7表示成formula_250和formula_251的线性和。重复进行迭代直到出现formula_5和formula_6： formula_254 formula_255 formula_256 最终，"g"可以表示成formula_5和formula_6的线性和：formula_238。贝祖等式以及以上证明都可以扩展至欧几里得整环。 主理想和相关问题. 贝祖等式提供了另一种定义formula_5和formula_6的最大公约数"formula_7"的方法。考虑形如formula_51（其中formula_52和formula_53是整数）的数的集合。因为formula_5和formula_6都可以被"formula_7"整除，所以这个集合中的所有元素都可以被"formula_7"整除。也就是说这个集合中的数都可以表示成"formula_7"的倍数，或者formula_5和formula_6的其他公约数的倍数。但是，只有最大公约数才是这个集合的元素。根据贝祖等式，有formula_238。换言之，当formula_274、formula_275时得出"formula_7"。任何其他的公约数都不是这个集合的元素，因为它们都不能被比它们大的"formula_7"整除。相反地，"formula_7"的任何倍数都属于这个集合，只要令formula_279、formula_280，便有： formula_281 所以，形如formula_51的数的集合等于"formula_7"的整数倍的集合。也就是说，任意两个数的线性和的集合等同于它们最大公约数的整数倍的集合。formula_5和formula_6的最大公约数叫做formula_5和formula_6的理想的生成元素。这个最大公约数的定义导出了两个现代抽象代数的概念：主理想（由单个元素生成的理想）以及主理想整环（其每一理想都是主理想的整环）。 这个结果可以解决某些实际问题。例如，考虑两个容积分别为formula_5和formula_6的量杯，其中formula_5和formula_6为正整数。通过加入或倒去"formula_52"倍第一个量杯的体积以及"formula_53"倍第二个量杯的体积的液体，任何体积为formula_51的液体都可以被量出（只要formula_51为正数）。根据贝祖等式，凡是可以被量出的液体，其体积一定是formula_5和formula_6的最大公约数"formula_7"的倍数。 扩展欧几里得算法. 贝祖等式的整数"s"和"t"可以通过扩展欧几里得算法算出。这个扩展算法在原有辗转相除法的基础上增加了两个递归等式： formula_299 formula_300 算法开始时： formula_301, formula_302 formula_303, formula_304 加上这两个递归式后，当算法终止于formula_305，贝祖等式的整数formula_236和formula_190分别由formula_308和formula_309给出。 这个算法的正确性可以用数学归纳法来证明。假设递归至第formula_310步是正确的，也就是假设： formula_311 在formula_312小于formula_70时皆成立。则第"formula_70"步运算得出以下等式： formula_315 因为formula_72和formula_71被假定是正确的，所以可以用formula_236和formula_190表示： formula_320 整理后得到第"formula_70"步的结果，和我们期望得到的结果一致： formula_322 矩阵法. 整数formula_236和formula_190也可以用矩阵运算得出。辗转相除法的计算过程： formula_325 formula_326 formula_327 可以写作2×2的商矩阵乘以一个2维余数向量： formula_328 令formula_329表示所有商矩阵的乘积： formula_330 这使辗转相除法化简为： formula_331 如要用formula_5和formula_6的线性和表示formula_7，可将等式两边同时乘以矩阵formula_329的逆矩阵。formula_329的行列式等于formula_337，因为它等于商矩阵的行列式的乘积，而每一个的行列式都是−1。因为formula_329的行列式不为零，最终的余数向量可以利用formula_329的逆矩阵解出： formula_340 由上式可以得出formula_341。 贝祖等式中的两个整数分别是formula_342、formula_343。矩阵法的效率可前文描述的辗转相除法的递归算法是相同的，每一步都有两次乘法和两次加法。 欧几里得引理和唯一分解. 贝祖等式对辗转相除法的很多应用都很重要，如证明自然数的唯一分解性质假设数字"L"可以写成两个因数formula_52和formula_53的乘积，即formula_346。如果另一个数formula_347与formula_52互素的数也能整除formula_349，那么"formula_347"必须整除"formula_53"，证明如下：如果"formula_52"和"formula_347"的最大公约数是1，则根据贝祖等式存在formula_236和formula_190使 formula_356。 两边都乘以"formula_53"： formula_358 因为"formula_347"整除等式右边，所以也应整除等式左边的"formula_53"。这个结果叫做欧几里得引理。如果一个素数整除"formula_349"那么它至少整除"formula_349"的一个因数。如果一个数"formula_347"互素于数列formula_364 中的每一个数，则"w"也一定互素于它们的乘积formula_365。 欧几里得引理足以证明每一个自然数的素数分解是惟一的。我们用反证法来证明，假设"formula_349"可以分别分解成formula_25个素数和formula_26个素数，即： formula_369 根据假设，每个素数formula_370都能整除"formula_349"，因此它必须能够整除某个formula_223；因为"formula_223"也是一个素数，所以formula_374。同理，对于每一个"formula_370"都存在一个"formula_223"与它相等。所以两种分解除了顺序不同以外是完全相同的。整数分解的惟一性在数学证明中有很多应用，下文将会提到。 线性丢番图方程. 丢番图方程是以亚历山大数学家丢番图的名字命名的一类方程，它的解被限制在整数范围。关于整数formula_377和formula_378的线性丢番图方程形如： formula_379 其中formula_5、formula_6、formula_32是已知整数。这个方程可以写成关于"formula_377"的同余式： formula_384 令formula_7为"formula_5"和"formula_6"的最大公约数，formula_5、formula_6都能被formula_7整除，故formula_391能够被"formula_7"整除。所以，"formula_32"一定能够被"formula_7"整除，不然方程就无解。方程两边若同时除以 formula_395，方程就变成了贝祖等式： formula_396 其中formula_236和formula_190可以用扩展欧几里得算法求解。所以这个丢番图方程的一个解即是： formula_399 总体而言，丢番图方程如果有解，就一定有无数个解。只需要考虑两个解formula_400 和formula_401： formula_402 或者可以写成： formula_403 所以相邻两个解的"formula_377"之间的差是formula_405，"formula_378"之间的差是formula_407。这样，所有的解都可以表示成： formula_408 当formula_409取遍所有整数时，方程所有的解都可以从formula_400计算出来。如果限制为正整数解 (formula_411, formula_412) 的话，那么解的数量就可能是有限的。有时候，这种对解的限制使丢番图方程在未知数个数比方程数更多的情况下仍然能有唯一解，而在允许实数解的线性方程组中，这种情况是不可能的。 乘法逆和RSA算法. 有限域是一个支持四种运算的数集。这四种运算也通称为加法、减法、乘法、除法，跟一般的四则运算有相同的性质，如交换律、结合律和分配律。举例来说，使用同余可以让13个数字的集合 formula_413 构成一个有限域。在这个域中，任何数学运算（加减乘除）都归约成13的模，例如 formula_414。对于任意素数formula_415，都可以定义这种有限域；使用更复杂的方法，也可以对素数"formula_415"的formula_417次方定义这样的有限域。有限域也叫做伽罗瓦域，其缩写为 formula_418 或formula_419。 在这样一个有"formula_417"个数的域中，任何非零元素formula_421都存在惟一乘法逆 formula_422使formula_423。这可以通过解同余式formula_424得出，或者也可以解与之等价的丢番图方程 formula_425 这个方程可用扩展欧几里得算法解出（参见上文）。在RSA算法中，寻找乘法逆是非常重要的一步，它决定了使用哪个数来解密信息。虽然RSA算法不使用域而是使用环，扩展欧几里得算法仍然可以用来求乘法逆。欧几里得算法也被应用于纠错码，例如，它可以代替伯利坎普－梅西算法解基于有限域的BCH码和里德-所罗门码。 中国剩余定理. 辗转相除法也可以用来解线性丢番图方程组。如在中国剩余定理中，整数可以表示成被formula_426个互素的数formula_427除留下的余数： formula_428 为了从formula_429的"formula_426"个余数formula_431中确定"formula_429"的值，我们将这些式子组合成单个线性丢番图方程，其中模数formula_433是所有模数"formula_427"的乘积，然后定义formula_435如下： formula_436 也就是，"formula_435"是除了"formula_427"以外所有模数的乘积。接着是关键的一步，寻找"formula_426"个数formula_440使： formula_441 有了这些数"formula_440"之后，整数"formula_429"可以用下式从余数formula_431中解出： formula_445 因为"formula_440"是"formula_435"的乘法逆，所以可以使用扩展欧几里得算法求出（见上一节）。 连分数. 辗转相除法和连分数有着紧密的关系。计算连分数的过程如下： formula_448 其中每个式子的右边最后一项都等于下一个式子的左边项的倒数。所以前两个式子可以组合成： formula_449 第三个式子可以代入分母中的formula_450： formula_451 每一步中，最后一项formula_452都可以用下一个式子代换，直至最后一个式子，结果是： formula_453 在上文的例子中计算了formula_454，其中商formula_455分别是2、3、7，所以分数 formula_456 可以写成如下连分数形式： formula_457 整数分解算法. 计算最大公约数是很多整数分解算法的重要步骤，如、Shor算法、以及。用辗转相除法算最大公约数效率非常高。而连分数分解法由于用到了连分数，所以也需要使用辗转相除法。 算法效率. 辗转相除法的计算效率已经被彻底研究过了。一个算法的效率可以用计算所需步数乘以每步计算的开销表示。加百利·拉梅于1884年指出，用辗转相除法计算两个数的最大公约数所需的步数不会超过其中较小数十进制下的位数formula_458的5倍。因为每一步的计算开销通常也是"formula_458"数量级的，所以辗转相除法的复杂度是formula_460。 计算步数. 计算两个自然数formula_461和formula_462的最大公约数所需的步数可以表示为formula_463。如果formula_461和formula_462的最大公约数是formula_466，formula_467，formula_468，而formula_469和formula_470是两个互素整数，那么： formula_471 这可以通过在辗转相除法的计算过程中的每一步都除以"formula_466"来证明。同样，当formula_461和formula_462同时乘以formula_475时，计算步数不变：formula_476。所以，对于数值上相近的数，如formula_463和formula_478，计算步数可能相差很大。 根据辗转相除法的递归性质可以得出另一个公式： formula_479 其中，根据定义有formula_480。 最差情况. 假设用辗转相除法求自然数formula_461和formula_462（formula_483）的最大公约数需要formula_484步，那么满足这一条件的formula_461和formula_462的最小值分别是斐波那契数formula_487和formula_488。这可以用数学归纳法证明。假设formula_489，"formula_462"整除"formula_461"，满足这一条件的formula_461和formula_462最小是formula_494、formula_495，正是formula_496和formula_497。现在假设这一规律对formula_498有效。一个需要formula_499步的算法的第一步是formula_500，第二步是formula_501。因为算法是递归的，它需要formula_498步才能算出formula_503，其中formula_462和formula_505的最小值是formula_506和formula_507。所以"formula_461"的最小值是当formula_509的时候，此时 formula_510。1844年，加百利·拉梅发现这个证明标志着计算复杂性理论的诞生。这也是斐波那契数列的第一个实际应用。 这个结果也证明了辗转相除法的运算步骤不会超过较小数十进制下的位数的五倍。因为如果算法需要"formula_484"步，那么"formula_462"一定大于或等于formula_488，也就是一定大于或等于formula_514，其中formula_515是黄金分割比。因为formula_516，所以formula_517。因为formula_518，formula_519，所以formula_520。所以，辗转相除法不会进行超过"O"("h")次除法，其中formula_458是较小数formula_462在十进制下的位数。 平均情况. 辗转相除法的平均步骤数有三种不同的定义。第一种定义是计算已知自然数formula_461和从0到formula_524范围内随机选取的自然数"formula_462"的最大公约数所需的时间formula_526： T(a) = \frac{1}{a} \sum_{0 \leq b 但是因为formula_463在连续整数间变化非常剧烈，所以formula_526的值也会显得很杂乱。 为了解决这个问题，第二种定义规定formula_529只要取遍其中所有和"formula_461"互素的数即可： \tau(a) = \frac{1}{\varphi(a)} \sum_{0 \leq b 在小于"formula_461"的数中，有formula_532个数与"formula_461"互素，其中formula_515是欧拉函数。在这个定义中，formula_529的函数值增长得平稳很多。 formula_536 误差项的增长率为formula_537，其中formula_538是无穷小量。公式中的常数formula_539等于： formula_540 其中formula_541是欧拉-马歇罗尼常数，formula_542是黎曼ζ函数的导数。公式最左边的formula_543由两个独立的方法确定。 因为第一种定义可以通过用第二种定义的求和来完成： formula_544 所以也可以由以下公式近似： formula_545 其中formula_546是冯·曼戈尔特函数。 第三种定义formula_547定义为从1到formula_470间随机选取formula_461和formula_462（均匀分布）时计算它们的最大公约数所需的平均步骤数： formula_551 将formula_526的近似公式代入，得到formula_547的近似： formula_554 每一步的计算开销. 在辗转相除法的每一步中，商formula_455和余数formula_556都通过formula_557和formula_558求出： formula_559 所以每一步的计算开销主要与计算商"formula_455"的算法有关，因为余数"formula_556"可以很迅速地从formula_557、formula_558和"formula_455"计算出来： formula_565 而计算一个formula_458位整数的除法的算法复杂度是"O"("h"("ℓ"+1))，其中"ℓ"formula_567是商的位数。 作为对比，辗转相除法原先的版本使用的是减法，因此效率要慢很多。进行一次除法等同于进行formula_568次减法（其中"formula_568"是商）。如果formula_461和formula_462的比很大，计算出的商也很大，也就需要进行很多次减法。但在另一方面，计算出来的商在大多数情况下都是非常小的，除法中得出一个确定的商"formula_568"的概率大约是formula_573。其中formula_574。比如，商是1、2、3、4的可能性分别是大约41.5%、17.0%、9.3%、5.9%。因为计算机计算减法要快于除法，特别是对于很大的数字，所以减法版本的辗转相除法的性能可以比得上除法版本。这也被运用于二进制最大公约数算法。 综合考虑算法需要的步数和每一步的计算开销，辗转相除法随两个数字formula_461和formula_462的平均位数成平方级的速度增长（formula_460）。设formula_578表示计算过程中的余数formula_579的位数，因为算法的步数formula_484随formula_458线性增长，所以算法的运算时间为： formula_582 其他算法的效率. 因为辗转相除法的高效率，它在实践中被广泛使用。作为对比，本段中介绍以下辗转相除法以外的其他最大公约数算法的效率。 计算两数formula_461和formula_462的最大公约数有一个效率很慢的算法：将"formula_461"除以从2到"formula_462"之间的每一个整数以计算出它们所有的公约数，其中最大的一个即是最大公约数。在这个算法中，步骤数随"formula_462"线性增长，也就是随输入数字的位数呈指数级增长。另一个很低效的算法是计算出两个数的所有素因数（见上文），最大公约数等于所有公共素因数的乘积。但是整数分解算法效率极低，很多现代的加密系统甚至依靠这种低效率来防止资料被破解。 除了辗转相除法之外，也有一些高效的算法存在，如二进制最大公约数算法将除法操作替换成了二进制的移位，以进一步提高用计算机运算时的效率。但是，这种改变并没有降低算法的复杂度（仍然是"O"("h"²)），虽然它在计算机上确实比辗转相除法快些。也可以通过只检视formula_461和formula_462的前几位数来进一步提高效率，不过效果并不明显。二进制版的算法还可以扩展到其它进制，效率最多可以提升五倍。 对于超过25,000位数的大数，有一种改进使算法复杂度降低至平方级以下，如Schönhage、Stehlé、Zimmermann等人提出的算法。这些算法利用2×2的矩阵（见上文）。这些亚平方级的算法复杂度通常是formula_590。 其他数系. 如上文所述，辗转相除法最早用来寻找两自然数的最大公约数，但其实它也可以被推广至实数，甚至是多项式、二次整数和赫尔维茨四元数。在这些数系中，辗转相除法甚至被用来证明一个重要特性：惟一分解，即这些数系中的数能够被惟一地分解成不可约元素（素数在这些数系的对应物）。惟一分解是数论中很多证明的基础。 有理数和实数. 辗转相除法可以被应用至实数，如欧几里得在几何原本第10卷中所说的那样。算法的目的是计算出实数formula_466，使已知实数formula_461和formula_462是它的整数倍：formula_467、formula_468，其中formula_469和formula_470是整数。这也就找到了formula_461和formula_462的整数关系，即找到整数formula_600和formula_601使formula_602。欧几里得使用辗转相除法来处理不可通约的长度。 实数的辗转相除法和整数的算法有两个区别。第一，余数formula_556是实数，虽然商formula_455仍然是整数。第二，算法不能保证在有限步内结束。如果能在有限步内结束，那么分数formula_605是一个有理数，即： formula_606 于是我们可以写出它的有限连分数形式：formula_607。如果算法无法结束，那么formula_605是无理数，可以写成无限的连分数形式：formula_609。无限连分数的一个例子是：黄金分割比formula_610和2的算术平方根：。通常，算法能够结束的可能性是很低的，因为对于实数formula_461和formula_462，几乎所有formula_605都是无理数。 如果算法不结束，也可以在第formula_70步时终止计算，得到近似连分数formula_615。终止时的"formula_70"越大，则近似越准确。连分数formula_617的分子和分母互素并满足下式： formula_618 formula_619 其中递归的初始值是formula_620, formula_621。formula_622是formula_605在分母是formula_624的数中最精确的有理数近似值： formula_625 多项式. 只含有一个变量formula_626的多项式可以和整数一样进行加法、乘法和分解为不可约多项式（也就是多项式中的“素数”）。两个多项式formula_627和formula_628的最大公约数formula_629定义为它们分解之后共有的不可约因式的乘积，这可以用辗转相除法进行计算。对于多项式的算法和整数的算法很相似，在每个步骤"formula_70"，计算出满足以下递归式的商多项式formula_631和余数多项式formula_632： formula_633 其中formula_634，formula_635。所选择的商式必须能使formula_636的首项系数和formula_637的相等，这样才能保证每个余数的次数小于前一个余数（formula_638）。因为非零多项式的次数是非负整数，并且在每一步都减小，所以辗转相除法的计算一定能在有限步内结束。最后一个非零余数即是两个多项式formula_627和formula_628的最大公约数。 例如，有如下两个四次多项式，都可以分解成两个二次多项式的乘积： formula_641 和 formula_642. formula_627除以formula_628得到余数： formula_645 在下一步中，formula_628除以formula_647得到formula_648。最终，formula_647除以formula_650得到的余数为0，所以formula_650是formula_627和formula_628的最大公约数，这和它们因式分解的结果相符合。 上文所述的很多应用也适用于多项式。辗转相除法可以解多项式的线性丢番图方程和中国剩余定理，也可以用来定义多项式的连分数展开式。 多项式的辗转相除法也有其他应用，如施图姆定理，一个用于计算多项式在给定区间内的实根个数的方法。这被应用于其他领域，如控制论的劳斯-赫尔维茨稳定性判据。 最后，多项式的系数不必局限于整数、实数、甚至复数。这些系数可以是其他域中的元素，如上文所述的有限域formula_654。从辗转相除法得出的结论也可以直接推广至这类多项式。 高斯整数. 高斯整数是满足formula_655的复数，其中formula_656和formula_657是普通整数，formula_658是虚数单位（-1的平方根）。通过在高斯整数中定义辗转相除法，根据上文贝祖等式可以证明高斯整数的惟一分解。高斯整数的惟一分解性质在很多应用中都很重要，如计算勾股数或者证明费马平方和定理。辗转相除法用于这些应用很方便，但并非必不可少，一些定理也可以由其他方式证明。 对于两个高斯整数formula_659和formula_660的辗转相除法和普通整数只有两个区别。像整数一样，算法的第formula_661步计算出商formula_455和余数formula_556： formula_565 其中formula_665，formula_666，每个余数都严格地小于前一个余数，formula_667。第一个区别即是：商和余数都是高斯整数，也就是复数，所以商"formula_455"是透过对实际比例（如复数formula_659/formula_660）的实部和虚部取最近似整数来找出的。第二个区别就是需要定义复数比较大小的方法。所以我们定义一个范数函数formula_671，以将高斯整数formula_672转换成普通整数来比较大小。在每个步骤"formula_661"中，余数的范数必须小于前一个余数的范数formula_674。因为范数是非负整数并且在每一步都减小，所以辗转相除法在有限步内一定能结束。最后一个非零余数即是formula_659和formula_660的最大公约数，即能同时整除formula_659和formula_660的整数中范数最大的一个。若把乘以formula_679或formula_680的所得结果考虑在内，那么可以说formula_659和formula_660的最大公约数是唯一的。 很多其他应用如线性丢番图方程、中国剩余定理都适用于高斯整数，高斯整数的连分数也可以用辗转相除法定义。 欧几里得整环. 如果一个支持两种二元运算（+ 和 ·）的元素的集合形成一个交换环"R"并且可以使用辗转相除法求最大公约数，那么这个集合叫做欧几里得整环。这两个二元运算不必是平常算数中的加法和乘法，它们可以是更广泛的概念，如群或幺半群中的运算。但是这些运算仍然需要遵守交换律、结合律、分配律。 推广之后的辗转相除法需要一个欧几里得函数，即一个将formula_683映射到非负整数集合的函数formula_684，使得对于"formula_683"中非零元素formula_461和formula_462，"formula_683"中存在formula_568和formula_690满足formula_691，formula_692。例如上文中用于高斯整数的范数函数。这个函数"formula_684"可以是数的绝对值或模，也可以是多项式的次数，只要辗转相除法计算过程中它的值不断减小就行，这样算法便能在有限步内结束。这非常依赖于非负整数的良序性，即每个非空的非负整数集合都有一个最小数。 任何欧几里得整环都满足算数基本定理：欧几里得整环中的数可以惟一分解。所以任何欧几里得整环都是惟一分解整环，但反之不然。欧几里得整环是GCD整环（任意两元素都存在最大公约数的整环）的子类。也就是说，在某些整环中，两元素存在最大公约数但却不能用辗转相除法计算。欧几里得整环都是主理想环，即其中每一个理想都是主理想，但并不是每个主理想环都是欧几里得整环。 欧几里得整环的惟一分解性质在很多场合都非常有用。例如，高斯整数的惟一分解性质可以方便地导出勾股数的公式，或者证明费马平方和定理。惟一分解性质也是加百利·拉梅于1847年基于约瑟夫·刘维尔的建议发表的证明费马最后定理的尝试中的关键部分。拉梅的尝试需要形如formula_694的数的惟一分解性质，其中formula_626和formula_696是整数，formula_697是1的formula_470次方根，即formula_699。虽然这对于某些"formula_470"成立（如formula_701时的艾森斯坦整数），但在其他情况下并非总是正确的。惟一分解性质在分圆域的失效使恩斯特·库默尔发明了理想数的概念，随后理查德·戴德金创造了理想的概念。#重定向 -{H|zh-cn:重定向;zh-tw:重新导向;}- 二次整数的惟一分解. 二次整数环对于解释欧几里得整环很有帮助。二次整数是高斯整数的推广，高斯整数中的虚数单位"i"被替换成一个复数ω。二次整数的形式是formula_702，其中formula_656和formula_657是整数，formula_705有两种形式，取决于参数formula_706。如果"formula_706"不等于四的倍数加一，那么： formula_708 如果"formula_706"等于四的倍数加一，那么： formula_710 如果二次整数环有像上文用来比较高斯整数的那样的范数函数，那么它就是规范欧几里德整环。只有当formula_711 −11, −7, −3, −2, −1, 2, 3, 5, 6, 7, 11, 13, 17, 19, 21, 29, 33, 37, 41, 57或73时，二次整数环才是规范欧几里德整环。formula_711 −1和−3时的二次整数分别叫作高斯整数和艾森斯坦整数。 但如果范数函数formula_684可以是任何欧几里得函数，那么使二次整数环是欧几里得整环的"formula_706"的可能值到目前为止还不确定。是欧几里得整环但不是规范欧几里德整环的第一个例子（formula_715）发表于1994年。温伯格于1973年证明，在广义黎曼猜想成立的前提下，formula_716时的二次整数环是欧几里得整环，当且仅当它是一个主理想环。 非交换环. 辗转相除法也可以应用至非交换环，如赫尔维茨四元数。令formula_659和formula_660表示这样一个环中的两个元素。他们有右公约数formula_719如果formula_720, formula_721（formula_722和formula_723是环中的元素）。同样，他们有左公约数"formula_719"如果formula_725, formula_726（formula_722和formula_723是环中的元素）。因为乘法不符合交换律，也就有两个版本的辗转相除法，一个计算右公约数，一个计算左公约数。例如对于右公约数，辗转相除法求最大公约数的第一步可以写成： formula_729 其中formula_730是商，formula_731是余数。对于左公约数，第一步过程是： formula_732 不管是哪一种，这个过程都会重复到最大左公约数或者最大右公约数计算出，像在欧几里得整环中一样，formula_731的“大小”一定小于formula_660，并且对于formula_731只有有限种的可能大小，这样才能保证算法能够结束。 由辗转相除法得出的大多数结果都适用于非交换环。例如，贝祖等式表明最大右公约数可以表示成α的倍数和β的倍数的和，即，存在formula_736和formula_737使： formula_738 对于最大左公约数，等式如下： formula_739 贝祖等式可以用来解非交换环的丢番图方程。 推广至其他数学结构. 辗转相除法有三个性质保证它不会永远进行下去。第一，它可以写成一系列递归式： formula_565 其中每一个余数都比前一个余数小，formula_741。第二，余数的大小有严格下限，如formula_742。第三，小于formula_743的数的数量是有限的。辗转相除法推广至其他数学结构，如和超限序数时仍保持这种性质。 辗转相除法的一个重要推广是代数几何中格罗布纳基的概念。像前文所述，formula_461和formula_462的最大公约数formula_466是它们的理想的生成元素。也就是说，对任何整数formula_600和formula_601，存在另一个整数formula_469使： formula_750 虽然这对一元多项式也成立，但是对多元多项式就不成立了。在多元多项式的情况下，生成元素的有限集合formula_751可以定义如下： formula_752 其中"formula_600"、"formula_601"和formula_755是多元多项式。任何这样的多元多项式formula_684可以表示成生成多项式的和加上惟一的余数多项式formula_690, 通常叫做多项式"formula_684"的一般形式。 formula_759 虽然商多项式formula_455可能不惟一。这些生成多项式的集合就叫做格罗布纳基。 参考文献. 来源. 外部链接. -{H|zh-hans:重定向;zh-hant:重新导向;}--{H|zh-cn:字符;zh-tw:字元;}--{H|zh-hans:文件; zh-hant:档案;}--{H|zh-hans:快捷方式; zh-hant:捷径;}--{H|zh-hans:项目;zh-hant:专案;zh-tw:计划;zh-hk:计划;zh-mo:计划;}--{H|zh-cn:计算机; zh-sg:电脑; zh-tw:电脑;}-