--本文证明部分转载自:/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是不能作为证明里的范围,有争议。文章搞得匆忙,也许还有些许错误,望读者勘误,谢谢。