Question

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

Answer 1

90與36的最大公約數(shù)為18
用輾轉(zhuǎn)相除法
令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.