本文地址：http://www.cnblogs.com/HarryGuo2012/p/4785167.html
最大公约数
想必大家小学就学过什么事最大公约数吧，现在给出一个数学上的定义：定义$g$是整数$a$和$b$的最大公约数，当且仅当$g$是同时整除$a$和$b$的数中最大的那个。
欧几里得算法
欧几里得算法可以写成如下简单的形式：
$$gcd(a,b) =egin{cases} a, & mbox{if }b=0 \gcd(b,a mod b), & mbox{if }b e0end{cases}$$
算法的证明
算法的过程可以写成如下的形式：
$$a=q_0b+r_0$$
$$b=q_1r_0+r_1$$
$$r_0=q_2r_1+r_2$$
$$r_1=q_3r_2+r_3$$
$$cdots$$
$$r_{k-1}=q_{k+1}r_k$$
显然，欧几里得算法的答案就是$r_k$。
先证明$r_k$能整除$a$和$b$：
$$ecause r_{k-1}=q_{k+1}r_k$$
$$ herefore r_{k-2}=q_kr_{k-1}+r_k=(q_{k+1}q_k+1)r_k$$
$$ herefore r_kmid r_{k-2}$$
$$cdots$$
$$ herefore r_kmid b$$
$$ herefore r_kmid a$$
$$ herefore gcd(a,b)=gge r_k$$
接下来证明$gcd(a,b)=g$能整除$r_k$
$$mbox{令} a=ng b=mg$$
$$ecause a=q_0b+r_0$$
$$ herefore r_0=a-q_0b=ng-q_0mg=(n-q_0m)g$$
$$mbox{同理}gmid r_k$$
$$ herefore gle r_k$$
$$mbox{由前面的证明我们知道} gge r_k$$
$$ herefore g=r_k$$
代码
int gcd(int a, int b){ return b==0?a:gcd(b,a%b); }