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为止.