Question

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

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

Answer 1

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

解:(1)319-261=58

261-58=203

203-58=145

145-58=87

87-58=29

58-29=29

∴319與261的最大公約數是29.

(2)因為兩數皆為偶數,首先除以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.