欧几里得算法用于求两个数的最大公约数,这篇博文力求以可视化的图形帮助读者理解欧几里得算法。
首先,简单介绍一下欧几里得算法
设a、b∈N*,我们规定gcd(a,b)代表a与b的最大公约数。
欧几里得算法的实质是gcd(a,b)=gcd(b,a%b),即a与b的最大公约数等于b与a%b的最大公约数。
通过迭代:gcd(a,b)=gcd(b,a%b)=gcd(a%b,b%(a%b))=gcd(b%(a%b),(a%b)%(b%(a%b)))…
至gcd(r,0)时,r即为a与b的最大公约数。
欧几里得算法的递归代码如下:
int gcd(int a,int b){
if(b==0)return a;
else return gcd(b,a%b);
}
以下对欧几里得算法通过图形和数学辅助证明gcd(a,b)=gcd(b,a%b)
首先明确我们要证明的两个东西
证明一:a%b的结果r依然能被gcd(a,b)整除,即gcd(b,a%b)>=gcd(a,b)
证明二:a%b的结果r与b不存在比gcd(a,b)更大的公因数,即gcd(b,a%b)<=gcd(a,b)
设a>b,gcd(a,b)=n,a%b=r.
首先证明证明一:
由条件易知n|a且n|b。(ps:n|a代表a能被n整除)
把a、b当作面积的大小,由于n|a且n|b,则a、b分别能够被有限个n填满。
故可以设a=xn,b=yn。
如下图:
由于a、b都是由有限个n组合而成,a%b是指a减去有限个b后的结果,而b由有限个n组成,故a%b等同于a减去有限个n的结果,故a%b依然能够被n整除。
这就像所有整数由有限个1构成,而整数减整数不会出现小数一样。
数学证明:
因为a=xn①,b=yn②,
所以a=kb+r③,其中k∈N*。
由③r=a-kb,带入①②得r=(x-ky)n④。
由④可知r是整数x-ky与整数n的乘积,即r也可以被n整除,即n|r,由于n|b,故gcd(r,b)>=n,而gcd(a,b)=n,a%b=r。
故gcd(b,a%b)>=gcd(a,b)。
证明一证明结束。
然后来证明证明二:
要证明a%b的结果r,与b不存在比gcd(a,b)更大的公因数,我们使用反证法
如果gcd(b,r)>gcd(a,b),则肯定存在一个整数m>n,使m|b且m|r。
同样将a、b比作面积。
我们知道,a%b将a分割成了余数外的面积(a-a%b)和余数面积(a%b)两部分
由于b|(a-a%b),且m|b,故m|(a-a%b),也就是说上图a左边的部分(a-a%b)可以被拆分为整数个m。
又由于m|r,即上图a右边的部分可以被拆分为整数个m。
等同于a可以被拆分为整数个m。
如下图:
即得到m|a,又因为m|b,所以gcd(a,b)=m>n,与gcd(a,b)=n不符。
所以m不存在,即gcd(b,a%b)<=n=gcd(a,b)。
数学证明:
因为m|b,b|(a-a%b)。
所以m|(a-a%b)。
又因为m|(a%b)
所以m|(a-a%b+a%b)=>m|a.
又因为m|b,m>n
所以gcd(a,b)=m,与条件gcd(a,b)=n不符。
所以m不存在
即gcd(b,a%b)<=n。
至此,证明二证明完毕。
由证明一gcd(b,a%b)>=gcd(a,b)和证明二gcd(b,a%b)<=gcd(a,b)得到gcd(b,a%b)=gcd(a,b)。
欧几里得算法至此证明完毕。
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)