Question

分別用輾轉(zhuǎn)相除法和更相減損之術(shù)求下列兩數(shù)的最大公約數(shù).

（1）261，319;

（2）1 734，816.

Answer 1

（1）輾轉(zhuǎn)相除法
319÷261=1(余58)
261÷58=4(余29)
58÷29=2(余0)
∴319與261的最大公約數(shù)是29.
更相減損之術(shù)：(261，319)→(261，58)→(203，58)→(145，58)→(87，58)→(29，58)→(29，29).
∴319與261的最大公約數(shù)是29

（2）輾轉(zhuǎn)相除法：
1 734÷816=2(余102)，
816÷102=8(余0)，
∴1 734與816的最大公約數(shù)是102.
更相減損之術(shù)：因?yàn)閮蓴?shù)皆為偶數(shù)，首先除以2得到867，408，再求867與408的最大公約數(shù).(867，408)→(459，408)→(51，408)→(51，357)→(51，306)→(51，255)→(51，204)→(51，153)→(51，102)→(51，51).
∴1 734與816的最大公約數(shù)是51×2=102.
[=HS(]對于第二個(gè)問題，用更相減損之術(shù)求解時(shí)，最后的結(jié)論有的同學(xué)可能會寫成51，而沒有乘以2，從而得出與用輾轉(zhuǎn)相除法不一樣的答案，51是它們的公約數(shù)，2也是它們的公約數(shù)，所以最大公約數(shù)就為51×2=102

使用輾轉(zhuǎn)相除法可依據(jù)m=nq+r，反復(fù)執(zhí)行，直到r=0為止；用更相減損之術(shù)就是根據(jù)m-n=r，反復(fù)執(zhí)行，直到n=r為止.