模逆元

在模 $n$ 的运算中，若整数 $b$ 满足 $ab\equiv 1(\mathrm{mod}n)$，就称 $b$ 为 $a$ 的模逆元（modular inverse）。它使“除以 $a$”有了准确含义：不是把余数写成普通分数，而是乘上逆元。

互素是存在的充要条件

若 $ab\equiv 1(\mathrm{mod}n)$，存在整数 $k$ 使 $ab-kn=1$。$a,n$ 的任何公约数都整除左边，故也整除 1，必须有 $gcd(a,n)=1$。反过来，若两者互素，贝祖等式给出 $ax+ny=1$，模 $n$ 后便有 $ax\equiv 1$。所以逆元存在当且仅当 $a$ 与 $n$ 互素。

例如 $3\cdot 4=12\equiv 1(\mathrm{mod}11)$，所以 4 是 3 模 11 的逆元。要解 $3x\equiv 5(\mathrm{mod}11)$，两边乘 4 得 $x\equiv 20\equiv 9(\mathrm{mod}11)$；代回 $3\cdot 9=27\equiv 5$。逆元按模 11 的剩余类唯一，因为两个逆元 $b,c$ 满足 $b\equiv b(ac)\equiv (ba)c\equiv c$。

不能随意约分

6 在模 15 下没有逆元，因为 $gcd(6,15)=3$。例如 $6x\equiv 6(\mathrm{mod}15)$ 有 $x\equiv 1,6,11(\mathrm{mod}15)$ 三个解；若直接“约掉 6”并写成 $x\equiv 1(\mathrm{mod}15)$，就漏掉了两个解。由扩展欧几里得算法求逆元前，先检查互素条件。

参考资料

• MIT，Mathematics for Computer Science，Modular Arithmetic 章节。
• MIT 18.781，初等数论讲义。
• 继续阅读：同余、贝祖等式、中国剩余定理。