扩展欧几里得算法 Bézout定理
- (ax + by = gcd(a, b))
证明
欧几里得算法执行到最后时，存在(x=1,y=0)，(a*1+0*0=gcd(a, 0))。
若(b>0)，(gcd(a,b)=gcd(b,a mod b))。假设存在(x, y)，满足(b*x+( a mod b)*y=gcd(b,a mod b))，则(bx+(a mod b)y=bx+y(a-b lfloor a/b
floor ) = b(x-b lfloor a/b
floor)+ay)，其中(x'=y,y'=x-b lfloor a/b
floor).
int exgcd( int a, int b, int &x, int &y ){
if( b == 0 ){ x = 1, y = 0; return a; }
int d = exgcd( b, a % b, x, y );
int z = x; x = y, y = z - y * ( a / b );
return d;
}