設兩個數是a和b(a & gt；B)，求A和B的最大公約數(A，B)的步驟如下:A除以B得到A ÷ B = Q...r1 (0 ≤ r1)。如果r1=0，那麽(a，b)= b；如果r1≠0，那麽除以r1，得到b ÷ r1 = q...r2 (0 ≤ R2)。如果r2=0，那麽(a，b)=r1，如果R2 \。最後壹個被除數是被除數的余數的除數是(a，b)。
例如:a=25，b=15，A/B = 1...10，B/10 = 1...5, 10/5 = 2 ...