Question

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

(1)80,36;(2)176,121.

Answer 1

解:(1)80與36都是偶數(shù),除以2得40,18,再除以2得20,9;9不是偶數(shù),則

20-9=11,11-9=2,9-2=7,7-2=5,5-2=3,3-2=1,2-1=1.

∴80與36的最大公約數(shù)為2×2×1=4.

(2)176-121=55,121-55=66,66-55=11,55-11=44,44-11=33,33-11=22,22-11=11.

∴176與121的最大公約數(shù)為11.

思路分析:用更相減損術(shù)求兩數(shù)的最大公約數(shù),就是依據(jù)r=a-b這個(gè)式子,反復(fù)執(zhí)行,即用大數(shù)減小數(shù),直到兩數(shù)相等.注意,當(dāng)兩數(shù)都是偶數(shù)時(shí),可先除以2,直到至少有一是奇數(shù)時(shí),再據(jù)上操作進(jìn)行.