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为止． 　　深化升华：通过上例可以发现用辗转相除法和更相减损术求得的最大公约数是相同的，但用辗转相除法的步骤较少，而用更相减损术运算简易，却步骤较多，在解题时应灵活运用．