Question

求90与36的最大公约数.

Answer 1

思路分析：可使用两种方法求它们的最大公约数.使用辗转相除法就是根据a=nb+r这个式子，反复执行，直到r=0为止.用更相减损术就是根据r=a-b这个式子，反复执行，直到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的最大公约数为18.

    上述过程也可以写为如下形式：

    90=2×36+18，

    36=2×18+0，

    所以90与36的最大公约数为18.

说明：两个数a，b的最大公约数一般写成（a，b），如90与36的最大公约数为18，写成（90，36）=18.

解法二：更相减损之术

    90-36=54

    54-36=18

    36-18=18

    18-18=0

    所以90与36的最大公约数为18.