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

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

更新时间： 2022年10月10日

48 次浏览

开启您的 职业生涯

完成课程获得认证

开始学习
广告