「辗转相除法」又叫做「欧几里得算法」,是公元前300年左右的希腊数学家欧几里得在他的著作《几何原本》提出的.利用这个方法,可以较快地求出两个自然数的最大公因数
对於两个自然数a和b,若存在正整数q,使得a=bq,则b能整除a,记作b|a,我们叫b是a的因数,而a是b的倍数.那麼如果c|a,而且c|b,则c是a和b的公因数.
由此,我们可以得出以下一些推论:
推论一:如果a|b,若k是整数,则a|kb.因为由a|b可知ha=b,所以(hk)a=kb,即a|kb.
推论二:如果a|b以及a|c,则a|(b±c).因为由a|b以及a|c,可知ha=b,ka=c,二式相加,得(h+k)a=b+c,即a|(b+c).同样把二式相减可得a|(b-c).
推论三:如果a|b以及b|a,则a=b.因为由a|b以及b|a,可知ha=b,a=kb,因此a=k(ha),hk=1,由於h和k都是正整数,故h=k=1,因此a=b.
辗转相除法是用来计算两个数的最大公因数,在数值很大时尤其有用
例如计算(546,429),由於546=1(429)+117,429=3(117)+78,117=1(78)+39,78=2(39),因此
(546,429)
(429,117)
(117,78)
(78,39)
39
网上找的，因为太多字了
匿名回答于2019-10-09 07:26:29
