乘法逆元三种求法总结

当我们取模的时候，被模数很大，无法直接计算其值，我们就会用取模运算的下面两个性质：

\displaystyle (a+b) \bmod x=((a \bmod x)+(b \bmod x))\bmod x \\ \displaystyle (a\ast b) \bmod x=((a \bmod x)\ast (b \bmod x))\bmod x

那么对于除法，是否也满足这个式子呢？

\displaystyle (a \div b) \bmod x=((a \bmod x)\div (b \bmod x))\bmod x

很显然也很遗憾，不满足。很容易找到反例：

\displaystyle (15 \div 5)\bmod 3=0 \not = ((15 \bmod 3)\div(5 \bmod 3))

那么当除数很大的时候怎么算呢？这就要用到乘法逆元了。

温馨提示：
在阅读本文之前建议先阅读：欧几里德算法与拓展欧几里德算法详解与欧拉函数、费马小定理与欧拉定理详解。
本文中有大量 KaTeX 公式，请确保浏览器支持，否则卡到超乎你想象。
Windows 可以在控制面板-程序-卸载程序-卸载\更新 Windows 组件中卸载IE浏览器。
本文中 (a,b) 或者 gcd(a,b) 表示a、b的最大公因数。

本文隶属⌈ 数论学习系列 ⌋。

乘法逆元的定义

设 $a,p \in Z$ ，满足 $(a,p)=1$ ，并且

\displaystyle ax \equiv 1 \pmod p

那么就称 x 是 a 模 p 的逆元。很像倒数，就是模了个 p。（维基百科搜索“乘法逆元”直接重定向到“倒数”……）

其实有另一种表示方式称 x 是 a 模 p 的阶，记作 $ord_p a$ .

乘法逆元的作用和证明

前面已经说了，乘法逆元可以在进行除法时让等式满足“分配律”。下面给出证明：

\displaystyle bx \equiv 1 \pmod p \iff bx = kp+1 \iff x=\frac {kp+1} b

代入 $ax \bmod p$ ，得到

\frac {a \cdot (kp+1)} b \bmod p = (\frac {kp+1} b + \frac a b )\bmod p = (a \div b) \bmod p

也就是说我们先求出 b 模 p 的逆元 x，这时 $ax \bmod p$ 就是 $(a \div b) \bmod p$ 的值。

乘法逆元的求法

线性求逆元

从简单而暴力的方法开始~ 当 p 很小的时候，我们可以枚举 1 到 p-1，判断这个式子是否成立：

ax \equiv 1 \pmod p

可以证明如果存在逆元，那么 $[1,p-1 ]$ 的范围内一定存在逆元。证明如下：

显然，任何大于 $p$ 的逆元都可以写成： $kp+x \bmod p$

\displaystyle ax \equiv akp+a \cdot (x \bmod p) \equiv a \cdot (x \bmod p) \equiv 1 \pmod p

综上，如果存在大于 $p$ 的逆元 $x$ ，则必定存在 $x \bmod p$ 也为其逆元。

（在这里我要把 DYT 同学批判一番，在他的博客数论初步：乘法逆元与几种求法 - CSDN博客里居然写道：“对于给定的 a 和 p，有且仅有一个数是它的逆元”这一显然错误的结论……）

扩展欧几里德求逆元

关于扩展欧几里德欧几里德的介绍参见：欧几里德算法与拓展欧几里德算法详解。

对于刚才的同余方程，可以变形为以下这个“裴蜀等式”：

ax+py=1

接下来就可以用扩展欧几里德解了。具体解法在欧几里德算法与拓展欧几里德算法详解这篇文章中已经详细介绍，这里不赘述。贴代码：

int exgcd(int a,int b,int &x,int &y){ //x、y变量用来传递求得的特殊解
    if(b==0){ //判断递归边界，b=0说明到底了
        x=1;y=0;
        return a;
    }
    int r=exgcd(b,a%b,x,y),t=x; //先递归把之前的都做完
    x=y;y=t-a/b*y;
    return r;
}

费马小定理/欧拉定理求逆元

费马小定理和欧拉定理在欧拉函数、费马小定理与欧拉定理详解这一篇里已经有详细的介绍。由于费马小定理是欧拉定理的一般情况，我们下面就只介绍欧拉定理求逆元。

当 $(a,n)=1$ 时，根据欧拉定理有

\displaystyle a^{\varphi(n)} \equiv 1 \pmod n

可以化成：

\displaystyle a \ast a^{\varphi(n)-1} \equiv 1 \pmod n

显然，这时候 $a^{\varphi(n)-1}$ 就是 $x$ 模 $p$ 的逆元。

可以根据欧拉函数公式求 $\varphi (n)$ ：

\displaystyle \varphi (n)=n\prod_{i=1}^r (1-\frac 1 {P_i})

值得一提的是当 $n$ 位质数时， $\varphi (n)=n-1$ 。这时候用欧拉函数求逆元就格外方便。

补充

以 O(N) 线性时间复杂度递推逆元的方法

参考

拖延症又犯了……这篇文章写了N天……
乘法逆元、扩展欧几里得算法、二元一次方程、a的n次方取余 - CSDN博客
 乘法逆元(除法取模) - CSDN博客
 逆元相关知识 - CSDN博客
 数论初步：乘法逆元与几种求法 - CSDN博客

本文章采用知识共享署名-非商业性使用-相同方式共享 4.0 许可协议进行许可。
欢迎转载，如有错误欢迎指出。
本文链接：https://old.skywt.cn/posts/inverse/