求以下两数的最大公约数
155 和 1385

已知： 155 和 1385。

求解： 我们需要求出这两个数的最大公约数。


解答

使用欧几里得除法算法求最大公约数

使用欧几里得引理得到：
  • $1385\ =\ 155\ \times\ 8\ +\ 145$

现在，考虑除数 155 和余数 145，并应用除法引理得到
  • $155\ =\ 145\ \times\ 1\ +\ 10$

现在，考虑除数 145 和余数 10，并应用除法引理得到
  • $145\ =\ 10\ \times\ 14\ +\ 5$

现在，考虑除数 10 和余数 5，并应用除法引理得到
  • $10\ =\ 5\ \times\ 2\ +\ 0$

余数已变为零，我们无法继续进行。

因此，1385 和 155 的最大公约数是此时此刻的除数，即 5。


所以，155 和 1385 的最大公约数是 5。

更新于： 2022年10月10日

2K+ 阅读量

开启您的 职业生涯

通过完成课程获得认证

开始学习
广告