Question

用更相減損術(shù)求下列兩數(shù)的最大公約數(shù).

(1)261,319  (2)1 734,816

Answer 1

思路分析：使用輾轉(zhuǎn)相除法可依據(jù)m=nq+r,反復(fù)執(zhí)行,直到r=0為止,亦可用如下的方法,直到余數(shù)為0;用更相減損術(shù)就是根據(jù)m-n=r,反復(fù)執(zhí)行,直到n=r為止.

解:(1)319-261=58

261-58=203

203-58=145

145-58=87

87-58=29

58-29=29

∴319與261的最大公約數(shù)是29.

(2)因?yàn)閮蓴?shù)皆為偶數(shù),首先除以2得到867,408,再求867與408的最大公約數(shù).

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的最大公約數(shù)是51×2=102.