当我们计算 a-b 时，可以将其视为 a+(-b) ；当我们计算 a/b 时，可以将其视为 a\times (1/b) ，也就是乘以其倒数。而逆元，可以理解为是在同余情况下的倒数。

简单来说，设 inv(b)为b\ mod\ m 意义下的逆元，则 a/b(mod\ m)=a\times inv(b)(mod\ m) 。

也就是说，在同余情况下，除去一个数，等于乘这个数的逆元。

由上面的式子可以推出 a/b(mod\ m)=a/b\times b\times inv(b)(mod\ m)， 也就是说b\times inv(b)\equiv1(mod\ m) 。

需要注意，逆元仅在所求数与模数互质时存在。

乘法逆元有两个性质：

①在模特定数的情况下唯一，不存在多解。

②乘法逆元是完全积性函数，也就是说 inv(a)\times inv(b)=inv(a\times b) 。

由费马小定理可得， a\times a^{p-2}\equiv1(mod\ p) 。

也就是说，当模数为质数，且需要求逆元的数与模数互质时，可通过快速幂直接求取其逆元。

参考代码：

看到 b\times inv(b)\equiv1(mod\ m) 你是否有想到什么？这正是拓欧例题中的同余方程一题的题目。此式可化为 b\times inv(b)\equiv1(mod\ m) 也就是 b\times inv(b)+k\times m=1 。

当 b,m 不互质时，无解。

当其互质时，将二者代入拓欧就可以求解出一组可行解。

为防负数，最后做一步处理 inv(b)=(inv(b)\%m+m)\%m 。

参考代码：

如果需要求一个大范围内所有数的逆元，再使用上面的方法会导致超时，所以还需要一种方法来线性求逆元。

我们设模数 m=k\times a+b 。

则可以化成同余式 k\times a+b\equiv0(mod\ m) 。

同余式两边同乘 inv(a)\times inv(b) ，得 k\times inv(b)+inv(a)\equiv0(mod\ m) 。

所以 inv(a)=-k\times inv(b)(mod\ m) 。

我们又由最开始对模数的定义式得到 k=m/a,b=m\%a 。

也就是说 inv(a)=-(m/a)\times(m\%a)(mod\ m) 。

观察上面的式子可以发现一个数的逆元可以由比它小的数的逆元递推而来。

所以就可以用于求范围内的逆元了。

线性求逆元的例题：【洛谷 P3811】

参考代码：