模逆元¶
模逆元也称为模倒数、数论倒数。如果
\[ ab \equiv 1 \pmod{n} \]
则称 \(b\) 为 \(a \bmod n\) 的逆元，记为 \(a^{-1}\)。
存在条件¶
\(a \bmod n\) 的逆元存在的充要条件是 \(a\) 与 \(n\) 互质。
求解方法 1¶
\(a \bmod n\) 的逆元存在时，\(a\) 与 \(n\) 互质。由 裴蜀定理，一定 \(\exists x,y \in \mathbb{Z}\)，使得
\[ ax+ny=1 \]
由于
\[ ax \equiv ax+ny \equiv 1 \pmod{n} \]
所以 \(x\) 就是一个答案，可以用 扩展欧几里得算法 求解。事实上，\(x+kn, k \in \mathbb{Z}\) 都是 \(a \bmod n\) 的逆元。
求解方法 2¶
由 欧拉定理（数论），\(a\) 与 \(n\) 互质时
\[ a^{\varphi(n)} \equiv 1 \pmod{n} \]
所以，\(a^{\varphi(n)-1}\) 是一个答案。
相关文章