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

• 中文名称 辗除法
• 别名 欧几里德算法

证明

　　设两数为a、b(b<a)，求它们最大公约数(a、b)的步骤如下:用a/b，得a/b=q......r1(0≤r)。若r1=0，则(a，b)=b;若r1≠0，则再用b/r1，得b/r1=q......r2 (0≤r2).若r2=0，则(a，b)=r1，若r2≠0，则继续用r1/r2,……如此下去，直到能整除为止。其最后一个非零余数即为(a，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 b<>0

　　return gcd(b, a mod b);

　　else

　　return a;

　　}

使用循环

　　function gcd(a, b) {

　　define r as integer;

　　while b ≠ 0 {

　　r := a mod b;

　　a := b;

　　b := r;

　　}

　　return a;

　　}

　　pascal代码(递归)

相关代码

　　具体标准C语言代码

最大公约数

　　求两数的最大公约数

　　function gcd(a,b:integer):integer;

　　begin

　　if b=0 then gcd:=a

　　else gcd:=gcd (b,a mod b);

　　end ;

　　其中"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 为输入数值的位数。

　　辗转相除法原理及其详细证明如下:

　　"辗转相除法"又叫做"欧几里得算法"，是公元前 300 年左右的希腊数学家欧几里得在他的著作《几何原本》提出的。利用这个方法，可以较快地求出两个自然数的最大公因数，即gcd 或叫做HCF 。

　　最大公约数(greatest common divisor，简写为gcd;或highest common factor，简写为hcf)

　　所谓最大公因数，是指几个数的共有的因数之中最大的一个，例如 8 和 12 的最大公因数是 4，记作gcd(8,12)=4。

整除性定义

　　在介绍这个方法之前，先说明整除性的一些特点(下文的所有数都是正整数，不再重覆)，我们可以这样给出整除性的定义:

　　对于二个自然数a和b，若存在正整数q，使a=bq，则a能被b整除，b为a的因子，a为b的倍数。

　　如果a能被c整除，并且b也能被c整除，则c为a、b的公因数(公有因数)。

　　由此我们可以得出以下推论:

　　推论1、如果a能被b整除(a=qb)，若k为正整数，则ka也能被b整除(ka=kqb)

　　推论2、如果a能被c整除(a=hc)，b也能被c整除(b=tc)，则(a±b)也能被c整除

　　因为:将二式相加:a+b=hc+tc=(h+t)c 同理二式相减:a-b=hc-tc=(h-t)c

　　所以:(a±b)也能被c整除

　　推论3、如果a能被b整除(a=qb)，b也能被a整除(b=ta)，则a=b

　　因为:a=qb b=ta a=qta qt=1 因为q、t均为正整数，所以t=q=1

　　所以:a=b

　　辗转相除法是用来计算两个数的最大公因数，在数值很大时尤其有用，而且应用在电脑程式上也十分简单。其理论如下:

　　如果 q 和 r 是 m 除以 n 的商及余数，即 m=nq+r，则 gcd(m,n)=gcd(n,r)。

　　证明是这样的: 设 a=gcd(m,n)，b=gcd(n,r)

　　a=gcd(m,n)

　　m能被a整除，并且n也能被a整除，则由推论1得:qn也能被a整除

　　由推论2得:m-qn也能被a整除

　　而m-qn=r，即r也能被a整除，所以a=b

　　或

　　b=gcd(n,r)

　　n能被b整除，并且r也能被b整除，则由推论1得:qn也能被b整除

　　由推论2得:qn+r也能被b整除

　　而m=qn+r，即m也能被b整除，所以a=b

　　例如计算 gcd(546, 429)

　　gcd(546, 429) 546=1*429+117

　　=gcd(429, 117) 429=3*117+78

　　=gcd(117, 78) 117=1*78+39

　　=gcd(78, 39) 78=2*39

　　=39