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