欧几里得算法（最大公因数）

---

问题##

欧几里德算法又称辗转相除法，用于计算两个正整数a，b的最大公约数。例如，gcd(50,15)=5。

---

证明##

其计算原理依赖于下面的定理：
定理：两个整数的最大公约数等于其中较小的那个数和两数相除余数的最大公约数。最大公约数（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<b），则r = a mod b
假设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），得证
注意:两种方法是有区别的。

---

代码##

    public static long gcd(long m, long n) {
        while (n != 0) {
            long rem = m % n;
            m = n;
            n = rem;
        }
        return m;
    }

分析##

如代码所示的算法计算gcd(M,N)，假设M>=N（如果N>M，则循环的第一次迭代，将他们互相交换）。算法连续计算余数直到余数是0为止，最后的非0余数就是最大公因数。因此，如果M=1989和N=1590，则余数序列为399,393,6,3,0。从而，gcd（1989,1590）=3。正如序列所表明的，这是一个快速算法。

估计算法的整个运行时间依赖于确定余数序列究竟有多长。显然logN看似像理想中的答案，但是根本看不出余数的值按照常数因子递减的必然性，因为我们看到余数从399仅仅降到393.事实上，在一次迭代中余数并不按照一个常数因子递减。然而，我们可以证明，在两次迭代后，余数最多是原始值得一半。

证明如果M>N，则M mod N < M/2如下：
存在两种情形。如果M<=M/2，则由于余数小于N，故定理在这种情况下一定成立。另一种情形则是M>M/2。但是此时M仅仅含有一个N，从而余数为M-N<M/2，定理得证。所以时间复杂度为O(logN)。