欧几里得算法用于求两个数的最大公约数，这篇博文力求以可视化的图形帮助读者理解欧几里得算法。 首先，简单介绍一下欧几里得算法 设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)。 欧几里得算法至此证明完毕。
