1.2.5　辗转相除法

求两个数的公约数方法中最著名的是欧几里得辗转相除法，简称辗转相除法.最早出现在公元前300年古希腊著名数学家欧几里得的《几何原本》（第VII卷，命题i和ii）中.而在中国则可以追溯至东汉出现的《九章算术》.

设两数为a，b（a>b），求a和b最大公约数（a，b）的步骤如下：

用a除以b，得a÷b=q……r1（0≤r1）.若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（b<a），用gcd（a，b）表示a，b的最大公约数，r=a mod b为a除以b以后的余数，k为a除以b的商，即a=kb+r.辗转相除法即是要证明gcd（a，b）=gcd（b，r）.

证　令c=gcd（a，b），则设a=mc，b=nc，根据前提可知r=a-kb=mc-knc=（m-kn）c，可知c也是r的因数，因此可以断定m-kn与n互质.否则，可设m-kn=xd，n=yd（d>1），则m=kn+xd=kyd+xd=（ky+x）d，即a=mc=（ky+x）dc，b=nc=ycd，故a与b的最大公约数为cd，而非c，与前面结论矛盾.

从而可知gcd（b，r）=c，继而gcd（a，b）=gcd（b，r）.

证毕.

对于辗转相除法的原理，也可以从以下三点来理解：

（1）如果a是任一整数，b是任一大于零的整数，则总能找到一整数q，使

a=bq+r

这里r是满足不等式0≤r<b的一个整数.

（2）从a=bq+r知道（a，b）=（b，r），即a和b的最大公因数与b和r的最大公因数是相等的.

这是因为对任意同时整除a和b的数u，有a=su，b=tu，它也能整除r，因为r=a-bq=su-qtu=（s-qt）u.

反过来每一个整除b和r的整数v，有，它也能整除a，因为.

因此，a和b的每一个公因子同时也是b和r的一个公因子，反之亦然.

（3）由于r是a除以b的余数，辗转相除法一直除下去，最后余数一定会得到0.

例1.2.2　a=1047，b=797，求gcd（a，b）.

解　　1047=1×797+250

797=3×250+47

250=5×47+15

47=3×15+2

15=7×2+1

所以　　gcd（a，b）=1

辗转相除法求gcd的算法描述如下：

/*功能：返回正整数m和n的最大公约数*/

（1）如果m>n则将m与n进行交换；

（2）如果n整除m则返回n，否则转（3）；

（3）temp=m，m=n，n=temp％n；

（4）转（1）.