本文共 1940 字，大约阅读时间需要 6 分钟。

\(a\)和\(b\)的最大公约数可以根据欧几里得算法求解，得到了\(GCD\)。那么，必定存在\(x\)和\(y\)，使得\(a*x+b*y=GCD\)。一个方程两个未知数，这是一个不定方程，存在多组解。欧几里得算法，即辗转相除算法停止的状态是：\(a=GCD,b=0\)。由此，我们可以联想到扩展欧几里得的最终状态上，即有\(a=GCD,b=0\)。那么此时\(x\)和\(y\)该为何值呢？\(x\)必定等于\(1\)，因为后一项不论

\(y\)取何值\(b*y\)已经等于\(0\)了。但是，我们还是要让\(y=0\)。因为可以通过欧几里得算法可以想到这是一个递归的过程，那么\(x\)和\(y\)也是递归的，回调的时候为了方便计算，同时出于最简化的目的，这里的\(y\)也就等于\(0\)了。那么就得到了：

假设刚开始的计算状态是：

作为等式1。

那么按照欧几里得算法的思想，下一步的状态就应该是：

作为等式2。

然后一直递归直到\(a=GCD,b=0\)。然后在回调，假设已经得到了\(x_1\)和\(y_1\)。那么我们就可以得到等式1与等式2之间的计算关系。因为：

作为等式3，

代入等式2就有：

即有：

作为等式4

与等式1相互对比可得到：

则这两个式子便是递推关系了。

给出代码：

Extended_Euclid(ll a,ll b,ll &x,ll &y)//ll long long{	int d;	if(b==0)	{		x=1;y=0;//最终状态		return a;	}	d=Extended_Euclid(b,a%b,x,y);	ll temp=x;//递推关系	x=y;	y=temp-a/b*y;	return d;//返回值依旧还是GCD}

那么扩展欧几里得有什么用呢？可以用来求乘法逆元。

对于下面用到的同余基础知识不清楚的，可以去看看：同余关系及其部分基本性质

什么就做乘法逆元？逆元 ：

\(x\)表示\(a\)的逆元。并且\(a*x ≡ 1 mod (m )\)注意：只有当\(a\)与\(m\)互质的时候才存在逆元。\(x\)叫做\(a\)关于\(n\)的乘法逆元。

因为

那么我们总可以找到\(p,q\)，使得

两边同乘\(a/b\)，就可以得到\(1-m(ap/b)=ax-m(aq/b)\)。就有\(a*x ≡ 1 mod (m)\)成立。等同于式子：

作为等式6。

为什么要互质才能存在解？因为不互质的话，无论如何取值，最小差值为\(2\)，怎么可能让左边的\(2\)等于右边的\(1\)。所以互质情况下才会存在解。就是说\(GCD(a,m)!=1\)的时候无解。这也是\(a*x+b*y=c\)有解的充要条件：\(c\%GCD(a,b)=0\)。约掉之后就变为了最简的形式，保证互质。例：\(5\)关于模\(14\)的乘法逆元是多少？

所以：

得到：\(5\)关于模\(14\)的乘法逆元是\(3\)。

理解这个过程有助于理解上述代码里面的回调过程。上面已经说了求乘法逆元相当于等式\(5\)中的\(x\)。那么这一切就变得简单了，代码依旧是上一段代码，只不过\(GCD=1\)。因为传参的时候&x，所以回调完成的时候就可以得到乘法逆元了。问题来了，求乘法逆元有什么用处？哈哈，中国剩余定理里面可是用到了！