欧几里得算法的证明

欧几里得算法是用来求两个正整数最大公约数的算法。古希腊数学家欧几里得在其著作《The Elements》中最早描述了这种算法,所以被命名为欧几里得算法

计算公式如下所示

(hexo 中 math渲染较慢，稍微等一下，如果还是没出来，就刷新(^▽^))

$$gcd(a,b) = gcd(b,a\ mod\ b)$$ $$下面来证明gcd(a,b) = gcd(b,a\ mod\ b)$$ $$证明：设a>b ,令a=kb+c，则c=a\ mod\ b\\ 设d=gcd（a，b）\ 则有 a=pd，b=qd\\ 故有：pd=kqd+c\ 则c=（p-kq）d\\ \begin{aligned} ∴gcd（b，a\ mod\ b)&=gcd（b，c）\\ &=gcd（qd，（p-kq)*d）\\ &=d * gcd（q，p-kq）\\ \end{aligned}\\ （反证法）下面来证明p与p-kq互质：\\ 假设q与p-kq不互质，则有q=mt，p-kq=nt\\ ∴ q=mt，p=（km+n）t\\ ∴a=mtd，b=（km+n）td\\ ∴gcd（a，b）=td 与gcd（a，b）=d矛盾\\ ∴假设不成立\\ ∴q与p-kq互质\\ ∴gcd（b，a\ mod\ b）=d=gcd（a，b）$$

计算机计算这个相当地简单：

int gcd(int a,int b)
{
    return b==0?a:gcd(b,a%b);
}