辗转相除法

辗转相除法的证明

辗转相除法的算法

辗转相除法的计算机代码

辗转相除法

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

辗转相除法的证明

证明：

令c=gcd(a,b),a>=b,

令r=a mod b

设a=kc，b=jc，则k，j互素，否则c不是最大公约数

据上，r=a-mb=kc-mjc=(k-mj)c

可知r也是c的倍数，且k-mj与j互素，否则与前述k，j互素矛盾,

由此可知，b与r的最大公约数也是c，即gcd(a,b)=gcd(b,a mod b)，得证。

辗转相除法的算法

算法

辗转相除法是利用以下性质来确定两个正整数 a 和 b 的最大公因子的：

1. 若 r 是 a ÷ b 的余数, 则

gcd(a,b) = gcd(b,r)

2. a 和其倍数之最大公因子为 a。

另一种写法是：

1. a ÷ b，令r为所得余数（0≤r<b）

若 r = 0，算法结束；b 即为答案。

2. 互换：置 a←b，b←r，并返回第一步。

辗转相除法的计算机代码

虚拟码

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

function gcd(a, b) {

if a mod b<>0

return gcd(b, a mod b);

else

return 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

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

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