辗转相除法原理怎么证明(辗转相除法原理)

您好,蔡蔡就为大家解答关于辗转相除法原理怎么证明，辗转相除法原理相信很多小伙伴还不知道,现在让我们一起来看看吧！

1、「辗转相除法」又叫做「欧几里得算法」,是公元前 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 网上找的。

2、因为太多字了。

本文就讲到这里，希望大家会喜欢。

标签：

版权声明：本文由用户上传，如有侵权请联系删除！