辗转相除原理

欧几里德算法又称辗转相除法，是指用于计算两个非负整数a，b的最大公约数。应用领域有数学和计算机两个方面。计算公式gcd(a，b) = gcd(b，a mod b)。

其计算原理依赖于下面的定理：

定理：两个整数的最大公约数等于其中较小的那个数和两数相除余数的最大公约数。最大公约数（Greatest Common Divisor）缩写为GCD。

gcd(a，b) = gcd(b，a mod b) (不妨设a>b 且r=a mod b ，r不为0)

证法一

a可以表示成a = kb + r（a，b，k，r皆为正整数，且r

假设d是a，b的一个公约数，记作d|a，d|b，即a和b都可以被d整除。

而r = a - kb，两边同时除以d，r/d=a/d-kb/d=m，由等式右边可知m为整数，因此d|r

因此d也是b，a mod b的公约数

假设d是b，a mod b的公约数， 则d|b，d|(a-k*b)，k是一个整数。

进而d|a.因此d也是a，b的公约数

因此(a，b)和(b，a mod b)的公约数是一样的，其最大公约数也必然相等，得证。

证法二

第一步：令c=gcd(a，b)，则设a=mc，b=nc

第二步：可知r =a-kb=mc-knc=(m-kn)c

第三步：根据第二步结果可知c也是r的因数

第四步：可以断定m-kn与n互素【否则，可设m-kn=xd，n=yd，(d>1)，则m=kn+xd=kyd+xd=(ky+x)d，则a=mc=(ky+x)dc，b=nc=ycd，故a与b最大公约数≥cd，而非c，与前面结论矛盾】

从而可知gcd(b，r)=c，继而gcd(a，b)=gcd(b，r)，得证

注意:两种方法是有区别的。

假设有两个数x和y，存在一个最大公约数z=(x，y)，即x和y都有公因数z，那么x一定能被z整除，y也一定能被z整除，所以x和y的线性组合mx±ny也一定能被z整除。（m和n可取任意整数）对于辗转相除法来说，思路就是：若x>y，设x/y=n余c，则x能表示成x=ny+c的形式，将ny移到左边就是x-ny=c，由于一般形式的mx±ny能被z整除，所以等号左边的x-ny（作为mx±ny的一个特例）就能被z整除，即x除y的余数c也能被z整除。

若不能整除，则将min{x，y}作为被除数，余数c作为除数，继续循环这个过程，直到余数c=0为止。为什么这样做可以得到结果因为在这个过程中，被除数和除数最大公约数始终没有变。分析如下：

设商为f，假设第十一步得到了结果，循环过程：x/y=f1…c1y/c1=f2…c2c1/c2=f3…c3……c8/c9=f10…c10c9/c10=f11…0如此，c10即为最大公约数。那么据第一段所述，可得：c9%c10=0，c8%c10=0，c7%c10=0……c1%c10=0，据此可说明被除数和除数最大公约数始终没有变。于是这样就得到了最大公约数了。

备注：两个整数的最大公约数等于其中较小的数和两数的差的最大公约数最小公倍数等于两个数的乘积除以最小公约数b能被a整除<=>b/a=c…0 (c为整数)b能整除a<=>a/b=c’…0(c为整数).