1、先用小的一個數除大的一個數,得第一個餘數;
2、再用第一個餘數除小的一個數,得第二個餘數;
3、又用第二個餘數除第一個餘數,得第三個餘數;
4、這樣逐次用後一個數去除前一個餘數,直到餘數是0為止.那麼,最後一個除數就是所求的最大公約數(如果最後的除數是1,那麼原來的兩個數是互質數)。