什么是GCD？
GCD是最大公约数的简称（当然理解为我们伟大的党也未尝不可）。在开头，我们先下几个定义：
①a|b表示a能整除b（a是b的约数）
②a mod b表示a-[a/b]b（[a/b]即为整除，如此一来便可以得到余数）
③gcd(a,b)表示a和b的最大公约数
④a和b的线性组合表示ax+by（x,y为整数）。我们有：若d|a且d|b，则d|ax+by（这很重要！）

线性组合与GCD
现在我们证明一个重要的定理：gcd(a,b)是a和b的最小的正线性组合。
证明：
设gcd(a,b)为d，a和b的最小的正线性组合为s
∵d|a且d|b，
∴d|s。
而a mod s=a-[a/s]s
         =a-[a/s](ax+by)
         =a(1-[a/s]x)-b[a/s]y
亦为a和b的线性组合
∵a mod s<s（s是最小线性组合），而a mod s是a和b的正线性组合

所以说a mod s并不是正线性组合（正数），它应该是个0，所以才得以让上式成立
∴a mod s=0，即s|a
同理由s|b
∴s为a,b的公约数
∴s<=d
∵d|s
∴d=s。证毕。

由这条定理易推知：若d|a且d|b，则d|gcd(a,b)

Euclid算法
现在的问题是如何快速的求gcd(a,b)。穷举明显不是一个好方法（O(n)），所以需要一个更好的方法。
首先我们先提出一个定理：gcd(a,b)=gcd(b,a-bx)（x为正整数）。

证明：
设gcd(a,b)=d,gcd(b,a-bx)=e,则
∵d|a,d|b
∴d|a-bx
∴d|gcd(b,a-bx)，即d|e
∵e|b,e|a-bx
∴e|bx+(a-bx)，即e|a
∴e|gcd(a,b)，即e|d
∴d=e。证毕。

这个定理非常有用，因为它能快速地降低数据规模。
当x=1时，gcd(a,b)=gcd(b,a-b)。这就是辗转相减法。
当x达到最大时，即x=[a/b]时（不能更大了，否则a-bx小于0），gcd(a,b)=gcd(b,a mod b)。这个就是Euclid算法。它是不是Euclid提出的我不知道，但听说是在Euclid时代形成的，所以就叫Euclid算法了。程序非常的简单：

function Euclid(a,b:longint):longint;
 begin
  if b=0 then exit(a)
         else exit(Euclid(b,a mod b));
 end;

Euclid算法比辗转相减法好，不仅好在速度快，而且用起来也方便。两种算法都有一个隐含的限制：a>=b。用辗转相减法时，必须先判断大小，而Euclid算法不然。若a<b，则一次递归就会转为gcd(b,a)，接着就能正常运行了。

扩展Euclid
前面我们说过，gcd(a,b)可以表示为a和b的最小的正线性组合。现在我们就要求这个最小的正线性组合ax+by中的x和y。这个可以利用我们的Euclid算法。
从最简单的情况开始。当b=0时，我们取x=1,y=0。当b≠0时呢？
假设gcd(a,b)=d，则gcd(b,a mod b)=d。若我们已经求出了gcd(b,a mod b)的线性组合表示bx‘+(a mod b)y‘，则(先求出gcd(b,a mod b)的线性组合，再替换，得到gcd(a,b)的线性组合)
gcd(a,b)=d
        =bx‘+(a mod b)y‘
        =bx‘+(a-[a/b]b)y‘
        =ay‘+b(x‘-[a/b]y‘)
那么，x=y‘，y=x‘-[a/b]y‘。这样就可以在Euclid的递归过程中求出x和y。

程序：

void exGcd(int a, int b, int &x, int &y)
　　{
    　　if(b == 0)
    　　{
        　　x = 1;
        　　y = 0;
       　　 return ;
    　　}
    　　exGcd(b, a % b, x, y);//一直递归到b=0后再回来。
    　　int t = x;
    　　x = y;
    　　y = t - a / b * y;//从递归返回回来之后依然用之前的a,b
　　}

我们现在还有一个问题：x,y是不是确定的？(不唯一)答案：不是。如果x,y符合要求，那么x+bk,y-ak(a*(x+bk)+b*(y-ak)=a*x+b*y)也符合要求。不确定的原因在于这一句：“当b=0时，我们取x=1,y=0。”实际上y可以取任何正整数,即本来有多种可能性，我们只取x=1,y=0这么一种情况。另外肯定有无数姐，毕竟一个方程式，两个未知数。

实际上，ax+by=c,与a(x+b/k)+b(y-a/k)=c等价，这里的K不是任意整数，假设d=gcd(a,b)，那么K只要可以被a,b整除，那么就可以得到新的解，因此K最大可以取为gcd(a,b)=d，对于x，在[0,b/d-1]区间有一个新的解。这里为了使区间尽可能的小，K应该尽可能地取更大。

不定方程ax+by=c
现在终于到了本文重点：解二元一次不定方程。看起来扩展Euclid算法是不定方程的一种特殊情况，实际上呢，不定方程却是用Euclid算法解的。
对于不定方程ax+by=c，设gcd(a,b)=d，如果ax+by=c有解，则d|c（因为d|a,d|b，这也是许多奥数题的切入点）。所以一旦d不是c的约数，那么 ax+by=c一定无解。当d|c时，先求出ax‘+by‘=d=gcd(a,b)的x‘和y‘（利用扩展Euclid），则x=x‘*c/d，y=y‘*c/d。（d=ax’+by’,c=ax+by，因此x，y与x’,y’存在倍数关系。）

由上一段可知， 只要ax+by=c有一个解，它就有无数个解。
Euclid算法还可以求解同余方程ax≡b(mod m)。这其实和不定方程ax+my=b没有区别。（不定方程和同余方程一般都有范围限制，这其实也很容易解决，就不说了）

其他
初等数论中最基础的就是GCD以及其相关问题了。实际上，更深层次的初等数论还包括：
◆中国剩余定理
◆Miller-Rabin素性测试
◆pollard rho算法 

math_Euclid