定义

若$a \in Z$ ，$(a,m)=1$ ，则在模$m$ 的意义下存在唯一的整数$a^{-1}$ ，使得$aa^{-1}=a^{-1}a \equiv 1(mod m)$ ，称$a^{-1}$ 为$a$ 在模$m$ 下的乘法逆元。

求一个数的逆元

求一个数$a$ 的逆元有两种方法，欧拉定理和拓展欧几里得算法。

欧拉定理

由欧拉定理$a^{\varphi(n)} \equiv 1(mod n)$ 得，$a \times a^{\varphi(n)-1} \equiv 1(mod n)$ ，因而$a^{\varphi(n)-1}$ 即为$a$ 在模$n$ 下的逆元。

通常情况下我们遇到的$n$ 为质数，此时等价于费马小定理$a^{n-1} \equiv 1(mod n)$ ，从而$a^{n-2}$ 为$a$ 在模$n$ 下的逆元。

$a^{\varphi(n)-1}$ 和$a^{n-2}$ 可以用快速幂求得，复杂度为$O(log_2n)$ 。

拓展欧几里得算法

拓展欧几里得可以求得模线性方程$ax+ny=(a,n)$的解，当$(a,n)=1$时，$x$即为$a$ 在$n$ 下的乘法逆元，复杂度为$O(log_2n))$ 。

求n以内的逆元

求$n$ 以内的逆元，用上述两种方法复杂度均为$O(nlog_2n)$ 。

算法描述

其实还有种复杂度为$O(n)$ 的算法：

令$Inv_a$为$a$在$n$下的逆元，则有
$$
Inv_x \equiv [(n - \lfloor \frac{n}{x} \rfloor ) \times Inv_{n%x}]\mod n
$$

算法证明

设$n=kx+r$，其中$0 \leqslant r < x$，

那么原式等于$Inv_x \equiv [(n-k) \times Inv_r] (mod n)$

$\Leftarrow r \equiv [(n-k) \times x] (mod n)$

$\Leftarrow r \equiv -kx(mod n)$

即$kx+r = n \equiv 0(mod p)$ 。