求两个数的最大公约数
——辗转相除法
已知两个数a和b，求他们的最大公约数。

解：若a>b,则用a除以b，得其余数t1;
再用b除以t1，得其余数t2；
再用t1除以t2，得其余数t3；
再用t2除以t3，得其余数t4；
…………
再用t n−1除以t n，得其余数t n+1；
最后t n除以t n+1，得其余数0；
按照上述运算，余数为0时停止，最后一个非零余数t n+1就是两个数的最大公约数。

若a<b，道理相同。

下面我们再来证明辗转相除法：
由上面的阐述我们可以得到，辗转相除法的证明可以转化为证明两个数的最大公约数等于这两个数中的较小者和两个数商的余数的最大公约数。

假设a>b,a除以b的商是t，余数是s，故只需证a和b的最大公约数等于b和s的最大公约数即可；
a=tb+s ①
设a和b的最大公约数是k,则a、b可以表示为：
a=km ②
b=kn ③
因k为最大公约数，故m和n互质
由①②③可得：
s=a-tb=km-ktn=k(m-tn) ④
所以k是b和s的一个公约数，接下来只需要证明n和m-tn互质，就可以证明k是b和s的最大公约数；
这里我们用反证法，假设n和m-tn存在最大公约数w（w>1）,则n 和m-tn可表示为：
n=wA ⑤
m-tn=wB ⑥
A和B互质；
由⑤⑥可得：
m=wB+tn=wB+twA=w(B+tA)
n=wA
m和n存在公约数w，这和m、n互质矛盾，所以假设不成立，所以n和m-tn互质。

所以k也是b和s的最大公约数。

故a和b的最大公约数等于b和s的最大公约数，此方法得证。