求最大公约数与最小公倍数的辗转相除法的证明..谢谢

发布网友 发布时间：2022-04-11 20:06

我来回答

共4个回答

热心网友 时间：2022-04-11 21:35

辗转相除法
<br>「辗转相除法」又叫做「欧几里得算法」,是公元前 300 年左右的希腊数学家欧几里得在他的著作《几何原本》提出的.利用这个方法,可以较快地求出两个自然数的最大公因数,即 HCF 或叫做 *.所谓最大公因数,是指几个数的共有的因数之中最大的一个,例如 8 和 12 的最大公因数是 4,记作 *(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,则 *(m,n)=*(n,r).
<br>证明是这样的:
<br>设 a=*(m,n),b=*(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,即 *(m,n)=*(n,r).
<br>例如计算 *(546, 429),由於 546=1(429)+117,429=3(117)+78,117=1(78)+39,78=2(39),因此
<br>*(546, 429)
<br>=*(429, 117)
<br>=*(117, 78)
<br>=*(78, 39)
<br>=39
最小公倍数就是2个数的积除以最大公约数

热心网友 时间：2022-04-11 22:53

证明84和35
用大数84除以小数35得2余14，
再用除数3514除以余数14得2余7，
最后用除数14除以余数7得2不余，
除数7就是84和35最大公约数
而最小公倍数是用84乘以35再除以7就是420

热心网友 时间：2022-04-12 00:28

证明84和35
用大数84除以小数35得2余14，
再用除数3514除以余数14得2余7，
最后用除数14除以余数7得2不余，
除数7就是84和35最大公约数
辗转相除法是算最大公约数用的，无法算最小公倍数。
呵呵

热心网友 时间：2022-04-12 02:19

对于a,b这两个数（a>b），肯定是有一个公约数1的，或者也可能有一个更大的公约数z。不管是1还是更大的，我们把他视为z。
a/b = n...c => a - b*n = c
因为a%z = 0,b%z = 0 => b*n%z = 0 => (a - b*n)%z = 0 => c%z = 0.
余数c也是a,b公约数z的倍数。所以a,b的公约数也是c的约数，所以说求a,b的公约数可以等价于求b,c的公约数。