Question

求90與36的最大公約數(shù).

Answer 1

思路分析：可使用兩種方法求它們的最大公約數(shù).使用輾轉(zhuǎn)相除法就是根據(jù)a=nb+r這個(gè)式子，反復(fù)執(zhí)行，直到r=0為止.用更相減損術(shù)就是根據(jù)r=a-b這個(gè)式子，反復(fù)執(zhí)行，直到r=0為止.

解法一：用輾轉(zhuǎn)相除法

    令m=90，n=36，

    m=2n+18，r=18.

    令m=36，n=18.

    又有36=18×2，

    即m=2n，

    此時(shí)r=0.

    令m=18，n=0.

    故90與36的最大公約數(shù)為18.

    上述過程也可以寫為如下形式：

    90=2×36+18，

    36=2×18+0，

    所以90與36的最大公約數(shù)為18.

說明：兩個(gè)數(shù)a，b的最大公約數(shù)一般寫成（a，b），如90與36的最大公約數(shù)為18，寫成（90，36）=18.

解法二：更相減損之術(shù)

    90-36=54

    54-36=18

    36-18=18

    18-18=0

    所以90與36的最大公約數(shù)為18.