扩展欧几里得算法

1、什么是GCD?GCD是最大公约数的简称(当然理解为我们伟大的党也未尝不可)。在开头，我们先下几个定义：a|b表示a能整除b(a是b的约数)amodb表示a-a/bb(a/b在Pascal中相当于adivb)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|so而amods=a-a/ss=a-a/s(ax+by)=a(1-a/sx)-ba

2、/sy亦为a和b的线性组合*.*amodss,amods不能是a和b的最小的正线性组合amods=0,即s|a同理由s|bs为a,b的公约数.s=dJd|sd=s。证毕。由这条定理易推知：若d|a且d|b,则d|gcd(a,b)Euclid算法现在的问题是如何快速的求gcd(a,b)。穷举明显不是一个好方法(0(n)，所以需要一个更好的方法。首先我们先提出一个定理：gcd(a,b)=gcd(b,a-bx)(x为正整数)。证明：设gcd(a,b)=d,gcd(b,a-bx)=e,贝IJd|a,d|b.d|a-bxd|gcd(b,a-bx)，即d|eJe|b,e|a-bxe|bx+(a-bx)，即

3、e|ae|gcd(a,b)，即卩e|dd=e。证毕。这个定理非常有用，因为它能快速地降低数据规模。当x=1时，gcd(a,b)=gcd(b,a-b)。这就是辗转相减法。当x达到最大时，即x=a/b时，gcd(a,b)=gcd(b,amodb)。这个就是Euclid算法。它是不是Euclid提出的我不知道，但听说是在Euclid时代形成的，所以就叫Euclid算法了。程序非常的简单：functionEuclid(a,b:longint):longint;beginifb=0thenexit(a)elseexit(Euclid(b,amodb);end;Euclid算法比辗转相减法好，不仅好在速度

4、快，而且用起来也方便。两种算法都有一个隐含的限制：a=b。用辗转相减法时，必须先判断大小，而Euclid算法不然。若ab，则一次递归就会转为gcd(b,a)，接着就能正常运行了。扩展Euclid前面我们说过，gcd(a,b)可以表示为a和b的最小的正线性组合。现在我们就要求这个最小的正线性组合ax+by中的x和y。这个可以利用我们的Euclid算法。从最简单的情况开始。当b=0时，我们取x=1,y=0。当bD0时呢？假设gcd(a,b)=d，贝Igcd(b,amodb)=d。若我们已经求出了gcd(b,amodb)的线性组合表示bx+(amodb)y，贝Igcd(a,b)=d=bx+(amod

5、b)y=bx+(a-a/bb)y=ay+b(x-a/by)那么，x=y，y=x-a/by。这样就可以在Euclid的递归过程中求出x和y。程序：functiongcd(a,b:longint):longint;varp,n,m:longint;beginifb=0thenbeginx:=1;y:=0;exit(a);endelsebeginp:=gcd(b,amodb);n:=x;m:=y;x:=m;y:=n-adivb*m;exit(p);end;end;我们现在还有一个问题：x,y是不是确定的？答案：不是。如果x,y符合要求，那么x+bk,y-ak也符合要求。不确定的原因在于这一句：“当b

6、=0时，我们取x=1,y=0。”实际上y可以取任何正整数。不定方程ax+by=c现在终于到了本文重点：解二元一次不定方程。看起来扩展Euclid算法是不定方程的一种特殊情况，实际上呢，不定方程却是用Euclid算法解的。对于不定方程ax+by=c,设gcd(a,b)=d,如果ax+by=c有解，则d|c(这也是许多奥数题的切入点)。所以一旦d不是c的约数，那么ax+by=c一定无解。当d|c时，先求出ax+by=d=gcd(a,b)的x和y，贝Ix=x*c/d,y=y*c/d。由上一段可知，只要ax+by=c有一个解，它就有无数个解。Euclid算法还可以求解同余方程axDb(modm)。这其实和不定方程ax+my=b没有区别。(不定方程和同余方程一般都有范围限制，这其实也很容易解决，就