初探Euclid算法

学过编程的人应该对Euclid算法（也叫辗转相除法）不陌生，许多书籍都把它作为递归的范例。
由于最近写到了一些涉及数论的题目，因此本人对其进行了更加深入的探究。

用Euclid算法求两个自然数的最大公约数
这是Euclid算法最常见的应用。它基于这么一个事实：
gcd(a,b)=gcd(b,a mod b)
《算法导论》中把这称作GCD递归定理，具体证明可以参考《算法导论》31.2小节。
31.2小节也讨论了Euclid算法的运行时间，结论Euclid执行中的递归调用次数是O(lgb)。

用Euclid求解二元一次不定方程的整数解
定理31.2：如果a和b不是都为0的任意整数，则gcd(a,b)是a与b的线性组合集合{ax+by}(x,y均为整数)中的最小正元素。
我们可以使用一个改进的Euclid算法（也叫做扩展Euclid算法）求解ax+by=gcd(a,b) 中x和y的值。
算法框架如下（其中d是a和b的最大公约数，x、y分别是a、b的系数）

ext-euclid(a,b)
  if(b = 0)
    then return (a,1,0)
(d',x',y')<--ext-euclid(b,a mod b)
(d,x,y)<--(d',y',x' - (a div b) * y')
return (d,x,y)

倒二行是Euclid算法的精髓。可以这样推导：
由GCD递归定理知d = gcd(a,b) = gcd(a, a % b)
那么就有d = ax+by = bx' + (a mod b)y'
又a mod b = a - (a div b) * b
因此d = ax + by = bx' + (a - (a div b) * b)y' = ay' + b(x' - a div b * y')
可知x = y'   y = x' - a div b * y'
当b为0时，显然x=1,y=0。

如果要求解不定方程ax+by=c（a,b,c均为整数）的整数解呢？

求解之前，要判断这个方程是否有整数解，这个方程有整数解的充要条件是gcd(a,b) | c。
然后，用扩展Euclid求解出ax+by=gcd(a,b)的一组解(x1,y1)。
那么(x1 * c / gcd(a,b),y1 * c / gcd(a,b))就显然是一组解了。
根据裴属定理，(x+b/gcd(a,b) * k,y + a/gcd(a,b) * k)，k为整数，也是这个方程的一组解。