目录

    GCD算法详解

1.原理

证法一

证法二

2.普通方法

3.递归算法

4.最美妙算法

    GCD算法是用于求解最大公约数的方法，利用了欧几里得算法，即辗转相除法。

    最重要的等式莫过于（核心中的核心）：gcd(a,b) = gcd(b,a mod b) (不妨设a>b 且r=a mod b ,r不为0)

    a可以表示成a = kb + r（a，b，k，r皆为正整数，且r1)，则m=kn+xd=kyd+xd=(ky+x)d，则a=mc=(ky+x)dc，    b=nc=ycd，故a与b最大公约数≥cd，而非c，与前面结论矛盾】

    从而可知gcd(b,r)=c，继而gcd(a,b)=gcd(b,r)，得证

    注意:两种方法是有区别的。