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为止．