辗转相除法求最大公约数的原理
【注】本文内容整理自网上下载的一个课件，具体来源不详。
在中国古代就有一个很好的算法来计算a,b的最大公约数（a,b）,称为辗转相除法，在西方称为Euclid算法。
下面通过计算（1397，2413）来阐述这一算法。
首先，我们用这两个数1397和2413中两个数中小的去除大的，得商为1，余数为1016。将原来两个数中大的2413扔掉，将1397作为大数，将余数1016作为新的小数。重复上面的过程：用1016去除1397，得商为2，余数为245。扔掉1397，将381作为除数，1016作为小的。用381去除1016，得商为2余数为254，扔掉1016，用254 去除381，得商为1 ，余数为127，再扔掉381，用127去除254，发现能整除，于是127就是最大公约数。
整个计算过程为：
2413=1397*1+1016，
1397=1016*1+381，
1016=381*2+254，
381=254*1+127，
254=127*2+0，
所以（1397，2413）=127。
为什么这样求出是就是最大公约数呢？下面对a,b为正整数（a>b）的情形给出说明。
根据定理10.2，商q和余r数满足a=bq+r,且0≤r ≤b-1. 若r=0，显然（a,b）=b;
若r≠0,由于a=bq+r，每个能整除b,r的整数都能整除a，当然能同时整除a,b,所以（b,r）|（a,b）;
另一方面，r=a-bq，每个能整除a,b的整数都能整除r, 当然能同时整除b,r, 所以(a,b)|(b,r).因此（a,b）=(b,r). 辗转相除法进行一步后，b取代原来的a，用r取代原来的b,最大公约数保持不变，因此我们的算法可以一直进行下去：
a=bq1+r1,
b=r1q2+r2,
r1=r2q3+r3,
…
rk-3=rk-2qk-1+rk-1,
rk-2=rk-1qk.
一旦出现rk-2=rk-1qk（即rk=0）,则有 rk-1=（rk-2，rk-1）=…=（r1，r2）=（b，r1）=（a，b）.
上述的求最大公约数的方法就称为辗转相除法。
推荐阅读
- 陇上秋二|陇上秋二 罗敷媚
- 我执意要等，是因为我相信你一定会来
- 你不可不知的真相系列之科学
- 与狗狗的相处公式
- 滚这个字
- 我与阳光有氧的相遇（中下）
- 幸福的人都是相似的，所有幸福的女人，都做好了这2点
- 以太坊中的计量单位及相互转换
- 七绝·大相国寺怀古
- 问（现在多少家产相当于30年前的万元户（））