是用来在已知a, b求解一组x，y，使它们满足贝祖等式： ax+by = (a, b) =d（解一定存在，根据中的相关定理）。扩展欧几里德常用在求解模及方程组中。

对于不完全为 0 的非负整数 a，b，gcd（a，b）表示 a，b 的最大公约数，必然

存在整数对 x，y ，使得 gcd（a，b）=ax+by。

设 a>b。

1，显然当 b=0，gcd（a，b）=a。此时 x=1，y=0；

2，a>b>0 时

设 ax1+ by1= gcd(a,b);

bx2+ (a mod b)y2= gcd(b,a mod b);

根据朴素的原理有 gcd(a,b) = gcd(b,a mod b);

那么我们就能得出

a * x1 + b * y1 = b * x2 + (a%b) * y2

其中a%b可以换成a-(a/b)*b

式子变成了

a * x1 + b * y1 = b * x2 + (a - (a / b) * b) * y2

因为我们要找x1 y1和x2 y2的关系

我们可以用待定系数法，按照这种方法把右边化成b * (x2 - (a / b) * y2) + a * y2

则等式变成了

a * x1 + b * y1 = a * y2 + b * (x2 - (a / b) * y2)

好，我们现在得出了下面两个等式：

x1 = y2（等式两边a的系数相同）

y1 = x2 - (a / b) * y2 （等式两边b的系数相同）

int exgcd(int a,int b,int &x,int &y){    if (b==0){        x=1,y=0;        return a;    }    int q=exgcd(b,a%b,y,x);    y-=a/b*x;    return q;}

扩展欧几里德算法不但能计算(a，b)的，而且能计算a模b及b模a的

乘法逆元，是指数学领域群G中任意一个元素a，都在G中有唯一的逆元a‘，具有性质a×a'=a'×a=e，其中e为该群的单位元

例如：4关于1模7的乘法逆元为多少？

4X≡1 mod 7

这个方程等价于求一个X和K，满足

4X=7K+1

其中X和K都是整数。

若ax≡1 mod f, 则称a关于1模f的乘法逆元为x。也可表示为ax≡1(mod f)。

当a与f互素时，a关于模f的乘法逆元有解。如果不互素，则无解。如果f为素数，则从1到f-1的任意数都与f互素，即在1到f-1之间都恰好有一个关于模f的乘法逆元。

例如，求5关于模14的乘法逆元：

14=5*2+4

5=4*1+1

说明5与14互素，存在5关于14的乘法逆元。

1=5-4=5-(14-5*2)=5*3-14

因此，5关于模14的乘法逆元为3。

乘法逆元也可用扩展欧几里得来求；