锐客网

  1. 首页 > it技术 > >

扩展欧几里得定理的证明和代码

1.欧几里得算法，gcd(a,b)为a b(a>b)的最大公约数，则gcd（a,b） = acd(b, a%b)
利用这个定理我们可以反复对ab模下去求得a和b的最大公约数
代码如下
int Gcd(int a, int b)
{
while (b > 0)
{
int tmp = a%b;
a = b;
b = tmp;
}
return a;
}


2.扩展欧几里得定理，对于a，b（a>b）一定存在整数 x y 使得xa + yb = gcd（a，b）
这个定理的证明，我看了下百度百科http://baike.baidu.com/link?url=oTITFw_5Sg-Ohf1XlYPbdvv8rYg-HgbRpod3l-G38ZvGuPkBK55EL4Wmv9g3qJ3Kg4pysMaiNNekCHK6NPjAYq，
百度百科上写的证明方法是这样的：


求解 x，y的方法的理解
设 a>b。
1，显然当 b=0，gcd（a，b）=a。此时 x=1，y=0；
2，a>b>0 时
设 ax1+ by1= gcd(a,b);
bx2+ (a mod b)y2= gcd(b,a mod b);
根据朴素的欧几里德原理有 gcd(a,b) = gcd(b,a mod b);
则:ax1+ by1= bx2+ (a mod b)y2;
即:ax1+ by1= bx2+ (a - [a / b] * b)y2=ay2+ bx2- [a / b] * by2;
也就是ax1+ by1 == ay2+ b(x2- [a / b] *y2);
根据恒等定理得：x1=y2; y1=x2- [a / b] *y2;
个人觉得这个证明很难理解，包括很多网站资料都是这样证明的，下面我自己用反证法证明了一下这个定理：
这个定理的反是对于a，b（a>b）对于任何整数 x y 使得xa + yb ~= gcd（a，b）
设四个序列（X1...Xk） (Y1...Yk)(A1...An) (B1...Bn) 其中a = A1， b =B1 ,X1 和 Y1是选择的任意的整数
即对于任意整数X1 Y1都有X1A1 + Y1B1 ~= GCD(A1,B1)
又因为A1 = A1/B1 * B1 + A1%B1
所以 X1(A1/B1 * B1 + A1%B1) + Y1B1 ~= GCD(A1， B1)
所以 (A1/B1 *X1 +Y1)B1 + X1 * A1%B1 ~= GCD(A1, B1)
我们设
Xn+1 = An/Bn * Xn + Yn
Yn+1 = Xn
An+1 = Bn
Bn+1 = An % Bn
则可以写成X2 A2 + Y2B2 ~= GCD(A1, B1) 又因为GCD(A1，B1) = GCD(B1, A1%B1) = gcd（A2, B2）
所以得到
X2A2 + Y2B2 ~= GCD(A2, B2)
同理可以递归下去得到
对于任意选择的初始x y，XnAn + YnBn ~= GCD(An, Bn)
因为An的序列和Bn的序列是一个符合欧几里得辗转相除的顺序，所以一定存在某个k，使得 Ak = Bk-1Bk = 0
那么Xk Ak + YkBk ~= gcd(Ak, Bk)
因为Bk = 0 所以GCD(Ak，Bk)= Ak
即对于任意选择的初始 X1 Y1都不存在 Xk Ak ~= Ak
显然这里选择能令Xk = 1的那个初始X1 Y1 就能使得XK aK = aK ,所以反证不成立，因此原定理得证。


从这个定理的证明过程中我们也得到了定理X1A1 + Y1B1 = gcd(A1, B1)（即XA + yb = gcd（a，b））中的两个整数xy的求解方法，这个xy是按照xn+1 = an/bn xn + yn 和 yn+1 = xn 最后使得某Xk为1 （当然yk此时为0）的那个初始的X1 Y1，我们现在把X和Y的序列反过来就可以求出来最初的X1 和 Y1。即xn-1 = ynyn-1 = xn- An-1/Bn-1*yn 并且我们知道Xk=1， Yk= 0 我们从k开始往回退，知道推到某个xY使得xa + yb = gcd（A,B）就得到了这个xy。
求扩展欧几里得定理的解的过程也为我们找到了一个求二元一次方程ax + by = c的重要解法，很容易我们可以推导出 如果c 可以整除 gcd（a，b），那么这个二元一次方程一定有整数解，整数解就是扩展欧几里得定理 ax+by =GCD(a,b)中解出来的xy再乘以gcd（a,b）/c (注意这只是一组解，可能还有其他解)
不管是欧几里得定理还是扩展欧几里得定理都是算法设计中常用的数学基础，代码一定要非常快速熟练的写出，下面是扩展欧几里得算法的代码(这个一直Xk Yk 往回求Xk-1 Yk-1的过程可以很容易的用一个递归来解决，这里用递归方便的原因是已知Xk Yk，虽然Xk-1 只依赖Yk ，但是Yk-1确还要依赖Ak-1和Bk-1,而Ak-1和Bk-1是和Yk-1在同一层求出来的，代码如下
void ExGcd(long a, long b, long& x, long& y)
{
if (b == 0)
{
x = 1;
y = 0;
return;
}
ExGcd(b, a%b, x, y);
long tmp = x;
x = y;
y = tmp - a / b * y;
}
这段代码的理解上就是计算第n层的扩展欧几里得，就是先计算n-1层的，然后利用 上面的n和n-1层间的x和y的关系
如果不用递归的话，也可以考虑先做一遍非递归的欧几里得辗转相除，过程中用数组或list存储每一层的ab，然后最后再从xk yk倒退xk-1和yk-1的过程中从list中拿到ak和bk。其实和上面方法是一样的计算过程。因为一个倒推的过程可以用一个正推的递归结构来表示


【扩展欧几里得定理的证明和代码】



??

    推荐阅读


    上一篇：星系大小对比

    下一篇：leetcode 133. Clone Graph（图的深复制）