在写证明过程之前，我们先回顾一下最大公约数gcd的欧几里得求法。
gcd，即最大公因数。为了书写方便，人们常习惯以gcd(a,b)表示a,b的最大公因数。那最小公倍数呢？我们知道若已知a,b,gcd(a,b),那么最小公倍数就自然等于a * b / gcd(a,b)。这里就不证明了。
我们接着看gcd，如何高效求gcd呢？目前最快的方法算是欧几里得算法了。
欧几里得算法其实很简单，已知a，b，其中a>b，求gcd(a,b)。
解：用b整除a，得到余数c，再用c整除b，得到余数d，再用d整除c，得到余数e……不断这样操作，最后直到没有余数为止。假设e再整除d，余数为0，则e为最大公因数。
列式子即为：
a = x1 * b + r1;
b = x2 * r1 + r2;
r1 = x3 * r2 + r3;
……
rn-1= xn+1 * rn + rn+1;
rn = xn+2 * rn+1 + 0;
若设a为r-1，b为r0，则通项公式即为rn-1 / rn = xn+1 rn + rn+1，最后一项为rn / rn+1 = xn+2 rn+1。
很容易理解，若某一步余数为0，则上一步的余数即为最大公约数。很容易证明该循环一定会终止，因为最坏的情况下a和b的最大公因数是1，那么任何一个数都是1的倍数，所以任何数取余1都为0，所以循环必会结束。
该算法历经千年，直到现在依然为求解gcd最高效的算法，gcd(a,b)最坏的情况下运算次数最多才是b位数的7位，这里就不详细介绍了。
那么为什么最后的结果就是最大公因数呢，接下来我们来证明一下。
假设g为gcd(a,b)，即g为g，b的最大公因数，则带到上式记为rn = xn+2 * g，这个式子g必然为rn的因数。
那再带到上一个式子，rn-1 = xn+1 * rn + g，由于g既是rn的因数，又是g的因数，则g是rn-1的因数。
再带到上一个式子，rn-2 = xn * rn-1 + rn，由于g是rn-1，rn的因数，所以g必然是rn-2的因数。
……
最终带到第一组式子中，即g既是a的因数，也是b的因数。
那如何证明它是最大公因数呢？
我们假设h为a，b的任意因数，则h整除a，且h整除b，带到第一个式子，则h整除r1，再带到第2个式子，h整除r2，再带到第3个式子，h整除r3……直到倒数第二个式子，h整除rn+1，即h整除g由于最后一个式子余数为0，那么既然g为a，b的因数，h为g的因数，则h<=g，故g为gcd(a,b)。
证毕。
