一、扩展欧几里德算法：
已知a, b求解一组x，y，使它们满足等式： ax+by = gcd(a, b) =d（解一定存在，根据数论中的相关定理）。
扩展欧几里德常用在求解模线性方程及方程组中。
证明：
ax+by=gcd(a,b);
1. (1) a = 0，ax+by = gcd(a,b) = gcd(0,b) = b,
此时x = 0(此时x的值是任意的)，y = 1；
(2)b = 0, ax + by = gcd(a,b) = gcd(a,0) = a,
此时x = 1，y = 0（此时y的值是任意的）；
2.a和b都不为0时
ax1 + by1 = gcd(a, b)
由欧几里德定理：gcd(a,b) = gcd(b, a%b)得
ax1 + by1 = gcd(a,b) = gcd(b, a%b) 即：
bx2 + a%by2 = gcd(b, a%b) = ax1 + by1
a % b = a - a/b*b;
ax1 + by1 = bx2 + (a - a/b*b)y2;
=bx2 + ay2 - a/b*b*y2;
=ay2 + b(x2-a/b*y2);
所以：x1 = y2, y1 = x2 - a/b*y2
扩展欧几里德算法代码：
void gcd(int a, int b, int &x, int &y)
{
if(b == 0)
{
x = 1;
y = 0;
r = a;//r为a、b的最大公约数
return ;
}
gcd(b, a%b, x, y);
int t = x;
x = y;
y = t - a / b * y;
}
二、欧几里德算法的应用
1.求方程ax + by = c的一种解
扩展欧几里德算法求得的x1,y1只是ax + by = gcd(a,b)中x和y的一个解
如果让求ax + by = c的一个解
ax1* z+ by1 * z = c * z;
使c * z = gcd(a,b),则z = c / gcd(a,b);
所以x = x1 * z = x1 * c / gcd(a,b), y = y1 * z = y1 * c / gcd(a,b);
x、y的解集为：
x = x1 + b / gcd(a,b) * t
y = y1 - a / gcd(a,b) * t;
(t 为任意值)
反证：
将x、y代入原式ax + by = gcd(a,b)中得：
a(x1 + b / gcd(a, b) * t) + b(y1 - a / gcd(a,b) * t) = gcd(a,b)
化简后得：
ax1 + by1 = gcd(a,b)
所以可得解集正确
2.ax≡b (mod n)的最小解，（ax % n ≡ b 相当与 ax + ny = b）
一般情况下，ax+by=1;得 x为a mod b 的逆元，y为 b mod a的逆元
若ax=1 mod f 则称a关于模f的乘法逆元为x。也可表示为ax≡1(mod f)。
当a与f互素时，a关于模f的乘法逆元有唯一解。如果不互素，则无解。如果f为素数，则从1到f-1的任意数都与f互素，即在1到f-1之间都恰好有一个关于模f的乘法逆元。
根据扩展欧几里德算法可求得ax + ny = b的一组解
x = b/gcd(a,n) * x1
要求其最小整数解，可根据同解x = x1 + n/gcd(a,n) * t;
s = n / gcd(a,n)
x%s得到最一个值x1,x1可能为负数，此时x%s还需要+s
加上s后可能就不是最小值了，所以还需要在对s取余
所以最小解最终为 x = (x % s + s) % s