Question

分別用輾轉相除法和更相減損之術求下列兩數的最大公約數.

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

Answer 1

分析：使用輾轉相除法可依據m=nq+r，反復執行，直到r=0為止；用更相減損之術就是根據m-n=r，反復執行，直到n=r為止.

解：(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.