什么是辗转相除法？

辗转相除法,
又名欧几里德算法乃求两个正整数之最大公因子的算法。两个整数的最大公约数是能够同时整除它们的最大的正整数。辗转相除法基于如下原理：两个整数的最大公约数等于其中较小的数和两数的差的最大公约数。

定义已经给过了~
证明：
设两数为a、b(b＜a)，求它们最大公约数(a、b)的步骤如下：用b除a，得a＝bq......r
1(0≤r)。若r1=0，则(a，b)＝b；若r1≠0，则再用r1除b，得b＝r1q......r2
(0≤r2).若r2＝0，则(a，b)＝r1，若r2≠0，则继续用r2除r1,……如此下去，直到能整除为止。其最后一个非零余数即为(a，b)。
给个例子具体来说吧：
8251＝6105＋2146，为了表示简单，我就用a=b+c表示这个吧
于是有c=a-b
那么如果有d|a,且d|b,就必然有d|a-b,也就是d|c,
可见a和b的公约数必然也是c的约数。
现在假设d是a,b的最大公约数，那么d也必然是c的约数，于是d是b,c的公约数，现在就要证明它是最大公约数——
因为a=b+c，于是b,c的公约数也必然是a的约数，假设(b,c)=e,（根据"d是b,c的公约数"知道d|e）那么有e|b+c,即e|a,可见e也是a,b的公约数，e|d,综上有e=d
可见(a,b)=(b,c)=d
这个思想一推广，就成了辗转相除法了。
求ab的最大公约数：
a=mb+c（带余除法：辗转相除法的步骤）
设n是a,b的最大公约数，则上式可写成na`=mnb`+c
所以，c=n(a`-mb`)，所以n也是c的公约数。
同理可证，bc的最大公约数也是a的公约数
这就是原理。