找出以下数字对的最大公约数
70 和 30

已知： 70 和 30。

求： 此处我们需找出给定数字的最大公约数。



解法

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

使用欧几里德引理得： 

  • $70\ =\ 30\ \times\ 2\ +\ 10$

现在，考虑除数为 30 和余数为 10，并应用除法引理可得

  • $30\ =\ 10\ \times\ 3\ +\ 0$

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

因此，70 和 30 的最大公约数是此阶段的除数，即 10。

所以，70 和 30 的最大公约数是 10。

更新于： 2022-10-10

101 查看次数

职业起航

完成课程获取认证

开始学习
广告