Question

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

Answer 1

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

解法一：用輾轉相除法

    令m=90，n=36，

    m=2n+18，r=18.

    令m=36，n=18.

    又有36=18×2，

    即m=2n，

    此時r=0.

    令m=18，n=0.

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

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

    90=2×36+18，

    36=2×18+0，

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

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

解法二：更相減損之術

    90-36=54

    54-36=18

    36-18=18

    18-18=0

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