--本文证明部分转载自：/ider/archive//11/16/gcd_euclid.html 作者： Ider
网上证明如他所说确实多，但他的我读完刚开始也没理解，后来查下其他资料，比较了下，还是他写的最好， 后面文字说明是我写的心得，建议先看他的证明，再结合我最后的思路。不懂得地方就举一个例子，还是好理解的，我觉得我这个版本应该是差不多解释的最好的了。
证明：gcd(m,n)=gcd(n mod m,m)成立，m,n为正整数，m>0.
证明：
1)1个常识：
如果 a≥b 并且 b≤a，那么 a=b.
2个前提：
1）只在非负整数范围内讨论两个数 m 和 n 的最大公约数，即 m, n ∈ N.
2）0可以被任何数整除，但是0不能整除任何数，即 ∀x(x|0) and ∀x(0|x).
2)1个引理：
假设 k|a, k|b，则对任意的 x,y ∈ Z， k|(xa+yb)均成立.
证明：
k|a => a=pk, k|b => b==qk (其中 p,q ∈ Z)
于是有 xa+yb=xpk+yqk=(xp+yq)k
因为 k|(xp+yq)k, 所以 k|(xa+yb)// 此处表示(xa+yb)被k整除。
3）gcd的Euclid算法证明：
命题：对任意 m, n ∈ N，证明gcd(m,n) = gcd(n, m mod n)
证明：
令 k=gcd(m,n),则 k|m 并且 k|n;
令 j=gcd(n, m mod n), 则j|n 并且 j|(m mod n);
对于m, 可以用n 表示为 m=pn+(m mod n);
由引理可知 j|m（其中 x=p,y=1）, 又 j|n，于是 j 是 m 和 n 的公约数（但不一定是最大的）;
因为 k 是 m 和 n 的最大公约数，所以必有 k≥j;
通过另一种表示形式：(m mod n)=m-pn,同理可得：
k|(m mod n),又k|n，于是 k 是 (m mod n) 和 n 的公约数（也不一定是最大的）;
同样由 j 是 n 和 (m mod n) 的最大公约数可以得到 j≥k;
由常识，得出结论 k=j,
即gcd(m,n) = gcd(n, m mod n) ，得证。
//思路：
先预证明k是n,m mod n 的公约数， 再证明j是m，n的公约数，最后由k≥j和j≥k得知k= j，又因为k，j本来就是gcd()，所以gcd(m,n) = gcd(n, m mod n)证明完毕。
//第一步：
先证明k>=j,怎么证明呢？由条件k=gcd(m,n)可知k已经是n,m的最大公约数！所以找一个比k小的约数不就好了吗！下面证明n,m的一个公约数：
由j=gcd(n, m mod n)可知j|n 并且 j|(m mod n) ：既表示n被j整除，(m mod n)被j整除。
所以找到一个n的约数是 j,再找到m的约数为 j即可。
由条件知m=pn+(m mod n);(为什么m=pn+(m mod n)?因为(m mod n)可以表示成m=pn+(m mod n)，m mod n表示m对n整除后的余数。)
再由j=gcd(n, m mod n)可知：n和(m mod n)均被j整除，就是说n和(m mod n)有一个公约数是j。所以由整除的结合律(引理)得 : pn+(m mod n)可以提出一个公约数j, 所以m必定被j整除。既m的约数为j。
其中m=pn+(m mod n)表示p倍的n加上1倍的(m mod n)=m,p为任意整数，1本来就是整数。所以m必定被j整除。
到此可知：n,m的一个公约数是j,因为 k=gcd(m,n)，所以k>=j。第一步证明完毕。
// 第二步：证明j>=k即可。
由条件 k|n可知：n有一个约数为k;再找到 m mod n 的约数也为 k即可。
m mod n =m-qn;(其中p,q均为整数)，又因为k=gcd(m,n)：m,n的公约数是k(最大的)，由整除的结合律可知：m mod n 被k整除，即找到了m mod n 的一个约数为k。
再由j=gcd(n, m mod n)所以j>=k;第二步证明完毕。
// 第三步：下结论
由于 k>=j，j>=k; 由常识可知k=j。再由k=gcd(m,n)且 j= gcd(n, m mod n)，故gcd(m,n) = gcd(n, m mod n)。证明完毕！
最后它有个m=0,n=0的特殊情况不在证明范围内，他们也有分歧。我是这么想的，0的时候两边最大公约数不都是0，肯定等式成立啊。可能你说m mod n ,不能整除啊，这里我也不清楚，我想是它0特殊，0的余数本来就是0，不用除。所以0是不能作为证明里的范围，有争议。文章搞得匆忙，也许还有些许错误，望读者勘误，谢谢。
