首页 > 代码库 > 欧几里得定理及扩展

欧几里得定理及扩展

 

  我们都知道欧几里得算法是用来快速求两个数的最大公约数的算法,效率较高:2O(logn)。

   我们先给出算法的实现:

 1 int gcd_1(int a, int b) 2 { 3     if(b==0) return a; 4     return gcd_1(b, a%b); 5 } 6  7 int gcd_2(int a, int b) 8 { 9     while(b)10     {11         int r = a%b;12         a = b;13         b = r;14     }15     return a;16 }
View Code

  要证明上述算法的正确性,我们就是证明如下定理的正确性:

  定理:设a,b,c,q,都是整数,且b>0。如果有a=b*q+c,那么gcd(a,b)==gcd(b,c)。

  证明:

  设 d=gcd(a, b), e=gcd(b, c). 于是存在整数k1, k2, k3, k4,使得a=d*k1, b=d*k2, b=e*k3, c=e*k4.

  那么 a = b*q+c = e*k3*q+e*k4=e*(q*k3+k4).所以e能整除a,从而e<=d;

  同理:c=a-b*q=d*k1-d*k2*q=d*(k1-k2*q),所以d能整除c,从而d<=e;综上,推出e==d---->gcd(a,b)==gcd(b,c)。

 

--------------------------- 分 割 线 -----------------------------------

 

  重点是扩展欧几里德定理,它在解线性同余式和中国剩余定理等很多方面都很有用。

  给你两个整数A,B让求一组整数解(X,Y)使得 Gcd(A,B)==A*X+B*Y。数论已经证明这组解一定存在。并且我们可以用扩展欧几里得算法求出解。

  首先给出欧几里得算法的证明过程:

  我们要求的是使 A*X+B*Y == Gcd(A, B)成立的X,Y值.

  根据欧几里得算法有:Gcd(A, B)==Gcd(B, A%B),那么我们可以递归求出X1 , Y1 满足:

  B*X1 + (A%B)Y1  == Gcd(B, A%B) == Gcd(A, B)。

  把A%B化简可得:

  B*X1 + (A-A/B*B)*Y1  == Gcd(A, B)----->

  B*X1 + A*Y1 - A/B*B*Y1  == Gcd(A, B) ------>

  A*Y1 + B*(X1 - A/B*Y1 )  == Gcd(A, B)

  所以推出:X = Y1

         Y = X1 - A/B * Y1

  代码如下:

#include <cstdio>#include <cstring>#include <cmath>using namespace std;__int64 Exgcd(__int64 a, __int64 b, __int64 &x, __int64 &y){    if(b==0)    {        x=1, y=0;        return a;    }    __int64 ans = Exgcd(b, a%b, x, y);    __int64 tp=x;    x = y;    y = tp - a/b*y;    return ans;}int main(){    __int64 a, b, x,y;    while(~scanf("%I64d%I64d", &a, &b))    {        __int64 ss = Exgcd(a, b, x, y);        printf("%I64d, %I64d, %I64d\n", x,y,ss);    }    return 0;}

 

扩展欧几里德算法的应用主要有以下三方面:

(1)求解不定方程;

(2)求解模线性方程(线性同余方程);

(3)求解模的逆元;

 

 

参考资料:《ACM国际大学生程序设计竞赛算法与实现》俞勇 主编

     《离散数学》John.Dossy Ablert.D.Otto著,原书第5版。

欧几里得定理及扩展