資料

• 歐幾里得算法
• 擴(kuò)展歐幾里得算法
• 擴(kuò)展歐幾里得算法應(yīng)用

歐幾里得算法

歐幾里得算法用于求兩個數(shù)的最大公約數(shù)

證明

設(shè) a > b, a = kb + r;
只需證明gcd( a, b ) = gcd( b, r );
設(shè) gcd( a, b ) = c;
a = m * c, b = n * c;
r = a - kb
  = ( m - nk ) * c;
要證gcd( b, r ) = c;只需證明 ( m - nk ) 與 n 互素，即gcd( m - nk, n ) = 1;
假設(shè)gcd( m - nk , n ) = d ( d > 1 );
那么 ( m - n k ) = xd, n = yd;
a = m * c
  = ( xd + nk )c 
  = ( x + ny )cd 
b = ycd;
如果d > 1 那么 gcd( a, b ) >= cd > c; 矛盾
所以 d = 1;
gcd( b, r ) = gcd( a, b );即證

算法

遞歸版:
int gcd(int a, int b)
{
 return (b == 0 ? a : gcd(b, a % b));
}

非遞歸版
int gcd( int a, int b )
{
    int t;
    while( b != 0 )
    {
        t = a % b;
        a = b;
        b = t;
    }
    return a;
}

擴(kuò)展歐幾里得算法

在求得a，b 的最大公約數(shù)的同時，還能求出一組解x，y，使其滿足貝祖等式
ax + by = gcd( a, b )

證明

設(shè) a > b, a = kb + r;
1. b = 0 時，
    gcd( a, b ) = a，x = 1，y = 0；
2. b != 0 時，
   設(shè) ax1 + by1 = gcd( a, b );
       bx2  + ( a % b )y2 = gcd( b, a % b );
   由歐幾里得算法得
   ax1 + by1 = bx2 + ( a % b )y2;
   化簡得
   x1 = y2;
   y1 = x2 -( a / b )y2;
   上述表明x1, y1 可由 x2, y2表示，以此遞歸下去，直到b = 0；可知必有解,
   即證.

算法

遞歸版
int exgcd(int a,int b,int & x,int & y){
    if(b == 0){
        //根據(jù)上面的推理1，基本情況
        x = 1;
        y = 0;
        return a;
    }
    //根據(jù)推理2
    int r = exgcd(b, a%b, x, y);
    int t = y;
    y = x - (a/b)*y;
    x = t;
    return r;
}

非遞歸版
int exgcd(int a,int b,int &x,int &y)
{
    int r = a % b;
    int x0, y0, x1, y1;
    x0 = 1; y0 = 0;
    x1 = 0; y1 = 1;
    x  = x1; y  = y1;
    while( r )
    {
        x = x0 -  a/b * x1;
        y = y0 -  a/b * y1;
        x0 = x1;
        y0 = y1;
        x1 = x;
        y1 = y;
        a = b;
        b = r;
        r = a % b;
    }
    return b;
}

非遞歸算法證明

根據(jù)歐幾里得算法
a = bq1 + r1; (1)
b = r1q2 + r2;(2)
r1 = r2q3 + r3;
....
ri-2 = ri-1*qi + r i;
....
rn-2 = rn-1*qn + rn; 
rn-1 = rn*qn+1 + 0;
因為對于ri>0,ri均是gcd(a, b)的倍數(shù)
所以每一步均存在 xi, yi, 使得 a xi + b yi = ri成立
ri = ri-2 - ri-1*qi
   = ( a*xi-2 + b*yi-2 ) - ( a*xi-1 + b*yi-1 )*qi
   = a*( xi-2 - qi*xi-1 ) + b( yi-2 - qi*yi-1 )
因為 ri = a xi + b yi;
xi = xi-2 - qi*xi-1;
yi = yi-2 - qi*yi-1;
直到求xn, yn;
因為 (1)和(2)式，
初始化 x0 = 1,y0 =0,x1=0,y1=1;

擴(kuò)展歐幾里得算法應(yīng)用

• 求解不定方程
• 求解模線性方程
• 求解模的逆元

求解不定方程

不定方程指ax + by = c，
a,b,c是整數(shù),證明ax+by=c在整數(shù)范圍內(nèi)有解的充要條件是 gcd( a, b )整除c.

證明:
設(shè)gcd( a,b )= d,則 d|c ,c = kd;
充分性:
ax0 + by0 = d,左右乘k，即可證明
必要性:
ax0 + by0 = c; d|a, b|a,那么 d|ax0 + by0,則 d|c即證  

算法

bool linear_equation(int a,int b,int c,int &x,int &y)
{
    int d=exgcd(a,b,x,y);
    if(c%d)
        return false;
    int k=c/d;
    x*=k; y*=k;    //求得的只是其中一組解
    return true;
}

求解模線性方程

模線性方程是指 ax≡b (mod n)

求解:
ax≡b(mod n)  等價于 ax = b + nk;
等價于 ax + ny = b;
當(dāng)b|gcd( a, n )時，有解
設(shè) gcd( a,n ) = d, ax0 + ny0 = d,
那么存在解 x = x0 * ( b/d ); 對模n有特解 x = x0*(b/d)( mod n );
易知，x， y有多解  
由x = ( b/a ) + ( n / a ) * y知，x的相鄰解的間隔時相同的
設(shè)間隔為dx
ax≡b(mod n) 
a(x+ dx) ≡b(mod n) 
相減  adx ≡ 0 ( mod n )  即 n | adx,且 a | adx.
那么最小的dx滿足 
adx = lcm( a, n )
       = a n / gcd( a, n )  
 dx = n / d;
可知,該方程對模n恰有d個不同的解(這個很顯然，但不會理論證明)

算法

bool modular_linear_equation(int a,int b,int n)
{
    int x,y,x0,i;
    int d=exgcd(a,n,x,y);
    if(b%d)
        return false;
    x0=x*(b/d)%n;   //特解
    for(i=1;i<d;i++)
        printf("%d\n",(x0+i*(n/d))%n);
    return true;
}

求解模的逆元

ax≡ 1 (mod n), gcd( a, n ) = 1, 只有唯一解，該解稱為 x 為 a 的對模 n 乘法的逆元。

byene.jpg