Processing math: 100%

使用欧几里得除法算法求最大公约数
(i) 135 和 225。
(ii) 196 和 38220。
(iii) 867 和 255。


已知: 
(i) 135 和 225。
(ii) 196 和 38220。
(iii) 867 和 255。
求解: 
我们需要求出给定数字的最大公约数。
解答
使用欧几里得除法算法求最大公约数
(i) 使用欧几里得引理得到: 
  • 225 = 135 × 1 + 90
现在,考虑除数 135 和余数 90,并应用除法引理得到
  • 135 = 90 × 1 + 45
现在,考虑除数 90 和余数 45,并应用除法引理得到
  • 90 = 45 × 2 + 0
余数已变为零,我们无法继续进行。 
因此,225 和 135 的最大公约数是此时除数,即 45
所以,135 和 225 的最大公约数是 45。
(ii) 使用欧几里得引理得到: 
  • 38220 = 196 × 195 + 0
余数已变为零,我们无法继续进行。 
因此,38220 和 196 的最大公约数是此时除数,即 196
所以,196 和 38220 的最大公约数是 196。
(iii) 使用欧几里得引理得到: 
  • 867 = 255 × 3 + 102
现在,考虑除数 255 和余数 102,并应用除法引理得到
  • 255 = 102 × 2 + 51
现在,考虑除数 102 和余数 51,并应用除法引理得到
  • 102 = 51 × 2 + 0
余数已变为零,我们无法继续进行。 
因此,867 和 255 的最大公约数是此时除数,即 51
所以,867 和 255 的最大公约数是 51。

更新时间: 2022年10月10日

48 次浏览

开启您的 职业生涯

完成课程获得认证

开始学习
广告