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

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

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

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

欧几里得除法引理算法

考虑两个数字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。

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