Question

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

被除数 / 除数 = 商 ...... 余数
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

或

辗转相除法
<br>「辗转相除法」又叫做「欧几里得算法」,是公元前 300 年左右的希腊数学家欧几里得在他的著作《几何原本》提出的.利用这个方法,可以较快地求出两个自然数的最大公因数,即 HCF 或叫做 gcd.所谓最大公因数,是指几个数的共有的因数之中最大的一个,例如 8 和 12 的最大公因数是 4,记作 gcd(8,12)=4.
<br>在介绍这个方法之前,先说明整除性的一些特点,注以下文的所有数都是正整数,以后不再重覆.
<br>我们可以这样给出整除以的定义:
<br>对於两个自然数 a 和 b,若存在正整数 q,使得 a=bq,则 b 能整除 a,记作 b | a,我们叫 b 是 a 的因数,而 a 是 b 的倍数.
<br>那麼如果 c | a,而且 c | b,则 c 是 a 和 b 的公因数.
<br>由此,我们可以得出以下一些推论:
<br>推论一:如果 a | b,若 k 是整数,则 a | kb.因为由 a | b 可知 ha=b,所以 (hk)a=kb,即 a | kb.
<br>推论二:如果 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).
<br>推论三:如果 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.
<br>辗转相除法是用来计算两个数的最大公因数,在数值很大时尤其有用而且应用在电脑程式上也十分简单.其理论如下:
<br>如果 q 和 r 是 m 除以 n 的商及余数,即 m=nq+r,则 gcd(m,n)=gcd(n,r).
<br>证明是这样的:
<br>设 a=gcd(m,n),b=gcd(n,r)
<br>则有 a | m 及 a | n,因此 a | (m-nq)(这是由推论一及推论二得出的),即 a | r 及 a | n,所以 a | b
<br>又 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).
<br>例如计算 gcd(546, 429),由於 546=1(429)+117,429=3(117)+78,117=1(78)+39,78=2(39),因此
<br>gcd(546, 429)
<br>=gcd(429, 117)
<br>=gcd(117, 78)
<br>=gcd(78, 39)
<br>=39
最小公倍数就是2个数的积除以最大公约数

Answer 1

在数学中，辗转相除法，又称欧几里得算法，是求最大公约数的算法。两个整数的最大公约数是能够同时整除它们的最大的正整数。辗转相除法基于如下原理：两个整数的最大公约数等于其中较小的数和两数的差的最大公约数。例如，252和105的最大公约数是21（252 = 21 × 12；105 = 21 × 5）；因为252-105 = 147，所以147和105的最大公约数也是21。在这个过程中，较大的数缩小了，所以继续进行同样的计算可以不断缩小这两个数直至其中一个变成零。这时，所剩下的还没有变成零的数就是两数的最大公约数。由辗转相除法也可以推出，两数的最大公约数可以用两数的整数倍相加来表示，如21 = 5 × 105 + (-2) × 252。

Answer 2

你写这堆东西里面不是说的很明白吗？

两个数的最小公倍数=这两个数的乘积除以它们的最大公因数。

辗转相除法就是用来求最大公因数的，不能直接用来求最小公倍数。但是利用二者的关系，可以很方便的求出最小公倍数。

Answer 3

辗转相除法最大的用途就是用来求两个数的最大公约数。

用（a,b）来表示a和b的最大公约数。
有定理： 已知a,b,c为正整数，若a除以b余c，则（a,b）=(b,c)。 （证明过程请参考其它资料）

例：求 15750 与27216的最大公约数。
解：
∵27216=15750×1+11466 ∴（15750，27216）=（15750，11466）
∵15750=11466×1+4284 ∴（15750，11466）=(11466,4284)
∵11466=4284×2+2898 ∴(11466,4284)=（4284，2898）
∵4284=2898×1+1386 ∴（4284，2898）=（2898，1386）
∵2898=1386×2+126 ∴（2898，1386）=（1386，126）
∵1386=126×11 ∴（1386，126）=126

所以（15750，27216）=216

辗转相除法比较适合用来求两个比较大的数的最大公约数

Answer 4

你有钻研的精神,加上严谨的治学态度,又精通数学领域的乘除加减,并能灵活运用小数点,更兼前后逻辑分明,汉语文化水平高超,且分析推断有理,让人欲辩难言,你在百度知道,也算屈才了

Answer 5

m÷n=p…r
n÷r=x…y
一直用除数除以余数直到余数为0.这时，除数是(m，n);
[m，n]=m×n÷(m，n)。