#
对于正整数 $a$ ，若存在 $s$ 使 $as\equiv1 \pmod{m}$
则记 $s$ 是 $a$ 在模 $m$ 下的逆元，即 $s\equiv a^{-1} \pmod{m}$
$a$ 存在逆元的充要条件为 $\gcd(a,m)=1$
费马小定理：若 $p$ 为质数，则对于任意整数 $a$ 有 $a^p \equiv a \pmod{p}$
威尔逊定理：若 $p$ 为质数，则有 $(p-1)! \equiv -1 \pmod{p}$
线性推逆元
设 $t=\left\lfloor\dfrac{m}{i}\right\rfloor,k=m \bmod i$ ，则
$\begin{aligned}ti+k&=\left\lfloor\dfrac{m}{i}\right\rfloor\times i + m \bmod i\&=(m-m\bmod i)+m \bmod i\&=m\end{aligned}$
移项，得到 $ti = -k + m$
对上式两边同时除 $ki$ ，得到 $tk^{-1} \equiv -i^{-1} \pmod m$
$\begin{aligned}
tk^{-1}&=-i^{-1}+am,a\in\mathbb{N}\
i^{-1}&=-tk^{-1}+am\
i^{-1}&=-tk^{-1} \bmod m
\end{aligned}$得到 $inv[i]=(-\left\lfloor\dfrac{m}{i}\right\rfloor)\times inv[m \bmod i] \bmod m$
再整理一下确保 $inv[i]$ 非负，最终得到
$\large{inv[i]=((m-\left\lfloor\dfrac{m}{i}\right\rfloor) \times inv[m \bmod i]) \bmod m}$
费马小定理求逆元
根据费马小定理可知， 若 $p$ 为质数，则对于任意整数 $a$ 有 $a^p \equiv a \pmod{p}$
那么对于质数 $p$ ，有 $a\times a^{p-1}\equiv a \pmod p$
因此 $a^{p-1} \equiv 1 \pmod p$
又因为 $a^{p-1}=a\times a^{p-2}$ ，所以 $a \times a^{p-2} \equiv 1 \pmod p$
所以 $a^{p-2}$ 是 $a$ 在模 $p$ 意义下的逆元。
扩展欧几里得算法求逆元
$ax \equiv 1 \pmod m$
$ax+bm=1$
可以使用扩展欧几里得算法求出一组 $x,b$ ，$x$ 即为 $a$ 在模 $m$ 意义下的逆元。
总结
求 $a$ 在模 $m$ 意义下的逆元时，若 $m$ 不是质数，则仅能使用 exgcd 求逆元；若 $m$ 是质数，则三种方法都可以使用。