##### 模逆元 - 模逆元 - **模逆元**是在[[同余]]或者[[模运算]]下的倒数. 给定一个[[整数]] $a$ 和模数 $m$, 如果存在一个整数 $x$ 满足 $a \cdot x \equiv 1 \pmod{m}$, 那么这个 $x$ 就叫做 $a$ 在模 $m$ 意义下的模逆元, 记作 $a^{-1} \bmod m$. 模逆元存在当且仅当[[公约数|最大公约数]] $\gcd(a, m) = 1$, 也就是说, $a$ 和 $m$ 必须[[互素]]. 可以用[[扩展欧几里得算法]]计算 - $a \cdot x \equiv 1 \pmod{m}$