欧几里得辗转相除法, 又称欧几里德算法（Euclidean algorithm），是求两个正整数之最大公因子的算法。
它是已知最古老的算法之一, 最早可追溯至公元前300年。
它首次出现于欧几里德的《几何原本》（第VII卷，命题i和ii）中，而在中国则可以追溯至东汉出现的《九章算术》。
它并不需要把二数作质因子分解。
编辑摘要
目录[隐藏]
1 概念
2 算法
3 伪代码
4 任意实数对的辗转相除法
5 多个数的辗转相除法
6 辗转相除法的步数估计——拉梅定理
辗转相除法- 概念
辗转相除法, 又名欧几里德算法（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)
=8
辗转相除法- 辗转相除法的步数估计——拉梅定理
拉梅定理：
设b≥a都是正整数，d(a)是a的十进制表示式中数字的个数，若n为辗转相除法计算最大公因数(a,b)的步数，则：
n≤5d(a)
比如在计算(326,78)中，由于d(78)=2，用拉梅定理至多需要10步，但是实际上只需要5步。
由此看来，拉梅定理的估计还是有些粗糙的。
