Question

分别用辗转相除法和更相减损之术求下列两数的最大公约数.

(1)261，319;(2)1 734，816.

Answer 1

解：(1)辗转相除法

319÷261=1(余58)

261÷58=4(余29)

58÷29=2(余0)

∴319与261的最大公约数是29.

更相减损之术：(261，319)→(261，58)→(203，58)→(145，58)→(87，58)→(29，58)→(29，29).

∴319与261的最大公约数是29.

(2)辗转相除法：

1 734÷816=2(余102)，

816÷102=8(余0)，

∴1 734与816的最大公约数是102.

更相减损之术：因为两数皆为偶数，首先除以2得到867，408，再求867与408的最大公约数.(867，408)→(459，408)→(51，408)→(51，357)→(51，306)→(51，255)→(51，204)→(51，153)→(51，102)→(51，51).

∴1 734与816的最大公约数是51×2=102.

[=HS(]对于第二个问题，用更相减损之术求解时，最后的结论有的同学可能会写成51，而没有乘以2，从而得出与用辗转相除法不一样的答案，51是它们的公约数，2也是它们的公约数，所以最大公约数就为51×2=102.

解析:

使用辗转相除法可依据m=nq+r，反复执行，直到r=0为止；用更相减损之术就是根据m-n=r，反复执行，直到n=r为止.