- 欧几里得算法
- 扩展欧几里得算法
- 扩展欧几里得算法应用
欧几里得算法
欧几里得算法用于求两个数的最大公约数
证明
设 a > b, a = kb + r;
只需证明gcd( a, b ) = gcd( b, r );
设 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;
假设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;
}
扩展欧几里得算法
在求得a，b 的最大公约数的同时，还能求出一组解x，y，使其满足贝祖等式
ax + by = gcd( a, b )
证明
设 a > b, a = kb + r;
1. b = 0 时，
gcd( a, b ) = a，x = 1，y = 0；
2. b != 0 时，
设 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){
//根据上面的推理1，基本情况
x = 1;
y = 0;
return a;
}
//根据推理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;
}
非递归算法证明
根据欧几里得算法
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)的倍数
所以每一步均存在 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;
扩展欧几里得算法应用
- 求解不定方程
- 求解模线性方程
- 求解模的逆元
求解不定方程
不定方程指ax + by = c，
a,b,c是整数,证明ax+by=c在整数范围内有解的充要条件是 gcd( a, b )整除c.
证明:
设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;
当b|gcd( a, n )时，有解
设 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的相邻解的间隔时相同的
设间隔为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
