模逆元：模运算中的除法

1. 为什么模运算不能直接做普通除法

在实数中，非零数 $a$ 的乘法逆元是 $1/a$。但模 $n$ 的运算对象是剩余类，普通小数通常不属于这个系统。

在模运算中，“除以 $a$”应理解为“乘以一个能够把 $a$ 乘回 1 的元素”。这个元素就是模逆元。

---

2. 模逆元的定义

如果存在整数 $x$，使

$$ax\equiv1\pmod n,$$

就称 $x$ 是 $a$ 模 $n$ 的乘法逆元（Modular Multiplicative Inverse），记作

$$a^{-1}\pmod n.$$

例如在模 7 下：

$$3 * 5=15\equiv1\pmod7,$$

所以

$$3^{-1}\equiv5\pmod7.$$

---

3. 逆元存在的充要条件

结论是

$$a\text{ 在模 }n\text{ 下可逆} \iff \gcd(a,n)=1.$$

从互质推出逆元存在

若 $\gcd(a,n)=1$，Bézout 等式保证存在整数 $x,y$，使

$$ax+ny=1.$$

两边模 $n$：

$$ax\equiv1\pmod n.$$

因此 $x$ 是 $a$ 的模逆元。

从逆元存在推出互质

若 $ax\equiv1\pmod n$，则存在整数 $k$，使

$$ax-1=kn.$$

整理为

$$ax-kn=1.$$

任何同时整除 $a,n$ 的整数都必须整除左侧，因此也必须整除 1。两者最大公约数只能是 1。

---

4. 用扩展欧几里得算法求逆元

求 $3$ 在模 $7$ 下的逆元，就是寻找

$$3x+7y=1.$$

因为

$$7=2 * 3+1,$$

所以

$$1=7-2 * 3.$$

这给出 $x=-2$。在模 7 下，

$$-2\equiv5\pmod7,$$

所以

$$3^{-1}\equiv5\pmod7.$$

负的 Bézout 系数需要归一化为常用代表元：

$$x_{\text{normalized}}=(x\bmod n+n)\bmod n.$$

---

5. 一个不存在逆元的例子

考察 2 在模 6 下是否有逆元：

$$\gcd(2,6)=2\neq1.$$

所以逆元不存在。直接观察也能发现，$2x$ 永远是偶数，不可能满足

$$2x\equiv1\pmod6.$$

这说明不能在模 6 的环境中随意约去因子 2。

---

6. 模除法的正确含义

如果 $b$ 在模 $n$ 下存在逆元，则

$$\frac ab\pmod n$$

表示

$$a * b^{-1}\pmod n.$$

这个写法有一个不可省略的前提：

$$\gcd(b,n)=1.$$

---

7. Python 验证

from math import gcd

n = 12

for a in range(1, n):
    inverse = None
    for x in range(1, n):
        if (a * x) % n == 1:
            inverse = x
            break
    print(a, gcd(a, n), inverse)

预期现象：只有满足 gcd(a, 12) == 1 的元素能够找到逆元。

这项枚举只能验证有限个具体例子；一般结论仍来自 Bézout 等式。

---

8. 自测

1. 模逆元的定义是什么？
2. 5 在模 12 下是否存在逆元？
3. 6 在模 15 下是否存在逆元？
4. 为什么模除法必须先检查最大公约数？

参考答案

1. 若 $ax\equiv1\pmod n$，则 $x$ 是 $a$ 模 $n$ 的逆元。
2. 存在，因为 $\gcd(5,12)=1$，且 $5 * 5=25\equiv1\pmod{12}$。
3. 不存在，因为 $\gcd(6,15)=3$。
4. 只有分母与模数互质时，分母才有模逆元。

上一篇：同余与剩余类。
下一篇：费马小定理与快速求逆。