首页 > 几何图形公式

欧几里得的除法引理:介绍和解法的例子

时间:2020-09-09 15:43:33

根据欧几里得的分部引理如果我们有两个正整数a和b,则存在唯一整数q- [R满足条件A = BQ + R,其中0 ≤[R <B 

欧几里得除法算法的基础是欧几里得除法引理。要计算两个正整数ab的最高公共因子(HCF),我们使用Euclid的除法算法。HCF是最大数,它精确地除以两个或多个正整数。这意味着,在将整数ab均除时,余数为零。

Euclid’s-Division-Lemma.jpg

现在让我们开始研究这种欧几里得算法。

欧几里得除法引理算法

考虑两个数字78和980,我们需要找到这些数字的HCF。要做到这一点,我们首先选择的最大整数,即,980,然后根据欧几里得司引理,A = BQ + R,其中0≤ [R  <  b ;

980 = 78×12 + 44

现在,这里a = 980,b = 78,q = 12和r = 44。

现在考虑除数78,余数44,再次应用欧几里得除法引理。

78 = 44×1 + 34

同样,考虑除数44和余数34,将欧几里得除法引理应用于44和34。

44 = 34×1 + 10

再次遵循相同的步骤,

34 = 10×3 + 4

10 = 4×2 + 2

4 = 2×2 + 0

如我们所见,余数已变为零,因此无法继续进行。因此,HCF是最后一步中剩下的除数b我们可以得出结论,980和78的HCF为2。

让我们尝试另一个示例,找到两个数字250和75的HCF。这里,整数越大,则250越大,因此,通过应用Euclid除法引理a = bq + r(其中0≤r <b),我们有

a = 250和b = 75

⇒250 = 75×3 + 25

通过将Euclid的除法算法应用于75和25,我们可以:

75 = 25×3 + 0

随着余数变为零,我们无法继续进行。根据该算法,在这种情况下,除数为25。因此,HCF 250和75为25。

示例:使用Euclid的除法算法找到81和675的HCF。

解决方案:较大的整数为675,因此,通过使用除法引理a = bq + r(其中0≤r <b),我们得到

a = 675和b = 81

⇒675 = 81×8 + 27

通过再次应用Euclid的除法算法,我们有了

81 = 27×3 + 0

由于余数变为零,我们无法继续进行。根据该算法,在这种情况下,除数为27。因此,HCF 675和81为27。

 

该算法在寻找数字性质方面有许多实际应用。还有更多的要学习的实数。

载入中…
点这里查看与之相关的计算

.

条评论

昵称: 需审核请等待!

密码: 匿名发表

验证码:

载入中…

.

.
分享到: