本文转自:http://www.cnblogs.com/ider/archive/2010/11/16/gcd_euclid.html,原文作者:Ider。内容有整理。
常识：如果 a≥b 并且 b≤a，那么 a=b.
前提：
1）只在正数(原谅为非负整数)范围内讨论两个数 m 和 n 的最大公约数，即 m, n ∈ N.
2）不考虑0的情况。(原文为处理0的特殊情况)
引理：
假设 k|a(表示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)
这上面的结论表示，对于都能被k整除的a和b,对a和b进行整数倍的乘法，并相加起来的结果仍然能够被k整除,可以理解为整除的结合率。
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);//即m可以表示为xn+y(m mod n)的方式,x为p,y为1
由引理可知 j|m（其中 x=p,y=1）, 又 j|n，于是 j 是 m 和 n 的公约数（但不一定是最大的）;
因为 k 是 m 和 n 的最大公约数，所以必有 k≥j;
证明第二节
通过另一种表示形式：(m mod n)=m-pn,同理可得：//即m mod n可以表示为xm+yn的方式，x为1,y为-p
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) ，得证。
转载请标明出处:i flym
本文地址:https://www.iflym.com/index.php/datastructure/201204240002.html