如何用辗转相除法求最小公倍数？？？被除数/除数=商......余数6497/3869=1......26283869/2628=1......12412628/1241=2......1461241/146=8......73146/73=2......0因此最大公约数为:73

　　如何用辗转相除法求最小公倍数？？？

　　被除数/除数=商......余数

　　6497/3869=1......2628

　　3869/2628=1......1241

　　2628/1241=2......146

　　1241/146=8......73

　　146/73=2......0

　　因此最大公约数为:73

　　最小公倍数=两数之积/最大公约数=6497*3869/73=25136893

　　或

　　辗转相除法

　　「辗转相除法」又叫做「欧几里得算法」,是公元前300年左右的希腊数学家欧几里得在他的著作《几何原本》提出的.利用这个方法,可以较快地求出两个自然数的最大公因数,即HCF或叫做gcd.所谓最大公因数,是指几个数的共有的因数之中最大的一个,例如8和12的最大公因数是4,记作gcd(8,12)=4.

　　在介绍这个方法之前,先说明整除性的一些特点,注以下文的所有数都是正整数,以后不再重覆.

　　我们可以这样给出整除以的定义:

　　对於两个自然数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.

　　辗转相除法是用来计算两个数的最大公因数,在数值很大时尤其有用而且应用在电脑程式上也十分简单.其理论如下:

　　如果q和r是m除以n的商及余数,即m=nq+r,则gcd(m,n)=gcd(n,r).

　　证明是这样的:

　　设a=gcd(m,n),b=gcd(n,r)

　　则有a|m及a|n,因此a|(m-nq)(这是由推论一及推论二得出的),即a|r及a|n,所以a|b

　　又b|r及b|n,所以b|(nq+r),即b|m及b|n,所以b|a.因为a|b并且b|a,所以a=b,即gcd(m,n)=gcd(n,r).

　　例如计算gcd(546,429),由於546=1(429)+117,429=3(117)+78,117=1(78)+39,78=2(39),因此

　　gcd(546,429)

　　=gcd(429,117)

　　=gcd(117,78)

　　=gcd(78,39)

　　=39

　　最小公倍数就是2个数的积除以最大公约数