Question

求78和36的最大公約數.

Answer 1

分析：利用輾轉相除法：計算出78÷36的余數６，再將前面的除數36作為新的被除數，36÷６=６，余數為０， 6就是78和36的最大公約數.理論依據： a=nb+r，得a,b與b,r有相同的公約數.利用更相減損之術：以兩數中較大的數減去較小的數，即78-36=42；以差數42和較小的數36構成新的一對數，對這一對數再用大數減去小數，即42-36=６,再以差數６和較小的數36構成新的一對數，對這一對數再用大數減去小數，即36-６=30,繼續這一過程,直到產生一對相等的數，這個數就是最大公約數.

解法一：78÷36=2(余6),

36÷６=６(余0),

所以，78和36的最大公約數是6.

解法二：(78,36)→(42,36)→(6,36)→(30,6)→(24,6)→(18,6)→(12,6)→(6,6).

所以，78和36的最大公約數是6.

綠色通道

    用輾轉相除法運算到余數為0為止，用更相減損之術運算到兩數相等為止，用輾轉相除法和更相減損之術求得的最大公約數各有優缺點，在解題時應靈活運用.