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． 　　更相減損術： 　　319－261＝58， 　　261－58＝203， 　　203－58＝145， 　　145－58＝87， 　　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， 　　459－408＝51， 　　408－51＝357， 　　357－51＝306， 　　306－51＝255， 　　255－51＝204， 　　204－51＝153， 　　153－51＝102， 　　102－51＝51， 　　∴1 734與816的最大公約數是51×2＝102． 　　綠色通道：通過上例可以發現用輾轉相除法和更相減損術求得的最大公約數是相同的，但用輾轉相除法的步驟較少，而用更相減損術運算簡易，卻步驟較多，在解題時應靈活運用．

提示：

使用輾轉相除法可依據m＝nq＋r，反復執行，直到r＝0為止，亦可用如下的方法，直到余數為0；用更相減損術就是根據m－n＝r，反復執行，直到n＝r為止．