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． 　　綠色通道：通過上例可以發(fā)現用輾轉相除法和更相減損術求得的最大公約數是相同的，但用輾轉相除法的步驟較少，而用更相減損術運算簡易，卻步驟較多，在解題時應靈活運用．

提示：

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