“辗转相除法”的意思、由来-中文百科全书

词条

辗转相除法

释义

§ 概念

辗转相除法, 又名欧几里德算法（Euclidean algorithm），是求两个正整数之最大公因子的算法。它是已知最古老的算法之一, 最早可追溯至公元前300年。它首次出现于欧几里德的《几何原本》（第VII卷，命题i和ii）中，而在中国则可以追溯至东汉出现的《九章算术》。它并不需要把二数作质因子分解。

我们用符号gcd(a,b)表示自然数a和b的最大公因数，在不引起误会的情况下(比如在涉及到解析几何的区间时，因为区间的表示与之一样)，也简写为(a,b)。

§ 算法

辗转相除法的实现，是基于下面的性质：

1：(a,b)=(a,ka+b)，其中a、b、k都为自然数

就是说，两个数的最大公约数，将其中一个数加到另一个数上，得到的新数组，其公约数不变，比如(4,6)=(4+6,6)=(4,6+2×4)=2。这里有一个比较简单的证明方法来说明这个性质：如果p是a和ka+b的公约数，p整除a，也能整除ka+b。那么就必定要整除b，所以p又是a和b的公约数，从而证明他们的最大公约数也是相等的。

还有另外一个性质也是很必要：

2：(0,a)=a

由这两个性质得到的，就是更相减损术：

(78,14)=(64,14)=(50,14)=(36,14)=(22,14)=(8,14)=(8,6)=(2,6)=(2,4)=(2,2)=(0,2)=2

基本上思路就是大数减去小数，一直减到能算出来为止。不过在平时的计算过程中，往往不必计算到最后一步，比如在上面的过程中，到了(8,6)，就已经能够看出其结果。

我们可以看到，在上面的过程中，由 (78,14)到(8,14)完全可以一步到位，因为(78,14)=(14×5+8,14)=(8,14)，由此就诞生出我们的辗转相除法。

用辗转相除法求(a,b).设r0=b，r1=a，反复运用除法算式，得到一系列整数qi，ri和下面的方程：r0=q1r1+r2，r2＜r1 　　　　　　　　　　(r2,r1)

r1=q2r2+r3，r3＜r2　　　　　　　　　　 (r3,r2)

r2=q3r3+r4，r4＜r3　　　　　　　　　　 (r4,r3)

………………

rn-3=qn-2rn-2+rn-1，rn-1＜rn-2　　　　 (rn-1,rn-2)

rn-2=qn-1rn-1+rn，rn-2＜rn-1　　　　　 (rn-1,rn)

rn-1=qnrn。 (rn,0)

相当于每一步都运用原理①把数字进行缩小，上面右边就是每一步对应的缩小结果，可以看出，最后的余数rn就是a和b的公约数。我们以一个题为例说明基本过程。

例题：求(326,78)

326=4×78+14　　 (78,14)

78=5×14+8 (14,8)

14=1×8+6 (6,8)

8=1×6+2 (6,2)

6=3×2 (0,2)

所以(326,78)=2。这和我们用更相减损术算出来的结果是一样的。

§ 伪代码

这个算法可以用递归写成如下:

function gcd(a, b)

if b = 0

return a

else

return gcd(b, a mod b)

或纯使用循环:

function gcd(a, b) {

define r as integer;

while b ≠ 0 {

r := a mod b;

a := b;

b := r;

}

return a;

}

其中“a mod b”是指取 a ÷ b 的余数。

例如，123456 和 7890 的最大公因子是 6, 这可由下列步骤看出：

a b a mod b

123456 7890 5106

7890 5106 2784

5106 2784 2322

2784 2322 462

2322 462 12

462 12 6

12 6 0

辗转相除法的运算速度为 O(n²)，其中n为输入数值的位数。

§ 任意实数对的辗转相除法

只要可计算余数都可用辗转相除法来求最大公因子。这包括多项式、复整数及所有欧几里德定义域（Euclidean domain）。辗转相除法不仅仅是针对于自然数对。

对于任意的两个实数n和m，只有当n/m为有理数的时候，n和m才有公因数，比如说π和2，这两个数就不会有公因数，有人可能第一反应说是1，不过很遗憾，1根本就不是π的因数，因为π除以1不是整数。我们先看其中的一种情况，那就是两个分数(也就是两个无理数)之间的公因数求法

1：两个有理数公因数的求法

A：设这两个数为n为m，将他们化成同分母的数，n=g/p，m=h/p，这里的p可以是任意的整数，并不要求一定是最小公分母，比如0.1和1/3，你可以将他们化成1/30，10/30，也可以化成2/60,20/60，这不影响他们的最大公因数。

B：求分子的最大公约数，即求出k=(g,h)

C：k/p就是n和m的最大公因数。

例题：求(1/3,2/7)

(1/3,2/7)=(7/21,6/21)=(7,6)/21=1/21

我们还可以这样来求：

(1/3,2/7)=(14/42,12/42)=(14,12)/42=2/42=1/21

2：n和m是无理数，但是n/m是有理数的最大公因数求法。

我们不妨设n/m=p/q，令n=ap，m=aq。求出p和q的最大公因数，即求出k=(p,q)，那么ak就是n和m的最大公因数。

例题：求(π,1/3π).

因为π/(1/3π)=3/1,π=3×1/3π,1/3π=1×1/3π，而(1,3)=1，故(π,1/3π)=1/3π。

3：当n/m是无理数时，(n,m)不存在。

实际上上面说了一大通，归根到底就一个东西：当需要求(n,m)时，你就想方设法从n和m提取公因式，就包括把分母和无理式都统统提出来，直到只剩下整数对，然后求出这个整数对的公约数即可，也就是下面的式子。

(an,am)=a(n,m)。其中a为任意实数，甚至可以是多项式。

§ 多个数的辗转相除法

我们可以如法炮制多个数的辗转相除法。利用的原理就是：(a,b,c,d,……)=(a,b+a,c+a,d+a,……)，我们先炮制前面的更相减损术，举例说明方法如下：

例题：求(4,18,22,16)

取最小的数4,其他的每一个数都与之相减，结果与4组成新的一组数，那么新数组与原数组的最大公因数相等，当出现零以后，排开零对剩下的数进行相同的处理。即：

(4,18,22,16)=(4,14+4,18+4,12+4)=(4,14,18,12)

=(4,10,14,8)=(4,6,10,4)=(4,2,6,0)=(0,2,2,4)=(0,2,0,2)=(0,0,2,0)=2

所以(4,18,22,16)的最大公因数为2.

同样的道理，在实际操作中，大可不必进行到最后一步，只需要进行到某一步就已经可以看出答案，比如在上面的过程中，到了(4,2,6,0)我想就应该可以看出其值为2了吧！

相应的，我们也可以炮制多个数的辗转相除法：

第一步，取最小的数a，然后用剩下的数除以a，得到的余数和a组成新数组，然后对新数组进行同样的动作；当出现零的时候，排除零，对其余的数进行相同的动作。直到最后只剩下一个非零数，这个数就是原数组的最大公约数。

例题2：求(120,168,328,624,320)

(120,168,328,624,320)

=(120,48,88,24,80)　　　　 (因为168除以120余48,328除以120余88,……)

=(24,0,0,16,8)

=(0,0,8,0,0)

§ 辗转相除法的步数估计——拉梅定理

拉梅定理：

设b≥a都是正整数，d(a)是a的十进制表示式中数字的个数，若n为辗转相除法计算最大公因数(a,b)的步数，则：

n≤5d(a)

比如在计算(326,78)中，由于d(78)=2，用拉梅定理至多需要10步，但是实际上只需要5步。由此看来，拉梅定理的估计还是有些粗糙的。