什么是辗转相除法??

辗转相除法

解释： 求两个正整数的最大公约数的算法。设两数为a、b(b＜a)，求它们最大公约数(a、b)的步骤如下：用b除a，得a＝bq�1＋r�1（0≤r�1＜b）。若r�1=0，则(a，b)＝b；若r�1≠0，则再用r�1除b，得b＝r�1q�2＋r�2（0≤r�2＜r�1）。若r�2＝0，则(a，b)＝r�1，若r�2≠0，则继续用r�2除r�1，……如此下去，直到能整除为止。其最后一个非零余数即为(a，b)。类似地，求两个多项式的最高公因式也可用此法。

Euclid辗转相除法是求最大公约数的标准算法，两数相除取余，重复直到除尽，剩余的商就是最大公约数了

定义已经给过了~
　　证明：
　　设两数为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的公约数
这就是原理。

辗转相除法
辗转相除法,又名欧几里德算法（Euclideanalgorithm）乃求两个正整数之最大公因子的算法。它是已知最古老的算法,其可追溯至前300年。它首次出现于欧几里德的《几何原本》（第VII卷，命题i和ii）中，而在中国则可以追溯至东汉出现的《九章算术》。它并不需要把二数作质因子分解。
[编辑]算法
辗转相除法是利用以下性质来确定两个正整数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，并返回第一步。
[编辑]虚拟码
这个算法可以用递归写成如下:
functiongcd(a,b){
if(a不整除b)
returngcd(b,amodb);
else
returna;
}
或纯使用循环:
functiongcd(a,b){
definerasinteger;
whileb≠0{
r:=amodb;
a:=b;
b:=r;
}
returna;
}
其中“amodb”是指取a÷b的余数。
例如，123456和7890的最大公因子是6,这可由下列步骤看出：
abamodb
12345678905106
789051062784
510627842322
27842322462
232246212
462126
1260
只要可计算余数都可用辗转相除法来求最大公因子。这包括多项式、复整数及所有欧几里德定义域（Euclideandomain）。
辗转相除法的运算速度为O(n2)，其中n为输入数值的位数