Question

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

261，319．

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． 　　思路分析：使用輾轉相除法可依據m＝nq＋r，反復執行，直到r＝0為止，亦可用如下的方法，直到余數為0；用更相減損術就是根據m－n＝r，反復執行，直到n＝r為止． 　　深化升華：通過上例可以發現用輾轉相除法和更相減損術求得的最大公約數是相同的，但用輾轉相除法的步驟較少，而用更相減損術運算簡易，卻步驟較多，在解題時應靈活運用．