什么是模逆元?
整数 a 关于模数 m 的模乘法逆元,是指满足 \((a \cdot x) \bmod m = 1\) 的整数 x。它相当于模运算中的"除法"运算,在数论、RSA 加密体制以及众多编码理论算法中都扮演着核心角色。本计算器利用扩展欧几里得算法来求出 x。
如何使用本计算器
输入数字 a 和模数 m(要求 m ≥ 2)。工具会返回位于 0 ≤ x < m 区间内的最小非负逆元 x,确认逆元是否存在,并显示 gcd(a, m) 的值。若 gcd(a, m) ≠ 1,则逆元不存在,结果显示为"None"(无)。
公式详解
只有当 \(\gcd(a, m) = 1\) 时逆元才存在,也就是 a 与 m 互质。扩展欧几里得算法会找出满足 \(a \cdot x + m \cdot y = \gcd(a, m)\) 的整数 x 和 y。当最大公约数为 1 时,将 x 对 m 取模即可得到逆元。 $$\text{a} \cdot x \equiv 1 \pmod{\text{m}} \quad\Longrightarrow\quad x = \text{a}^{-1} \bmod \text{m}$$ 如果结果为负数,则加上 m 将其归一化为正值。
实例演算
求 3 关于模 11 的逆元。我们需要找出满足 \(3x \equiv 1 \pmod{11}\) 的 x。逐一试算可知, $$3 \times 4 = 12 = 11 + 1$$ 因此 \(12 \bmod 11 = 1\)。所以 x = 4。扩展欧几里得算法得出的结果完全相同,且 \(\gcd(3, 11) = 1\),证实了逆元确实存在。
分步讲解:手算扩展欧几里得算法
模 m 的乘法逆元是满足 \(a \cdot x \equiv 1 \pmod{m}\) 的数 x。只有当 \(\gcd(a, m) = 1\) 时它才存在。扩展欧几里得算法分三步求出它。
- 反复相除。 用 m 除以 a,再用上一步的除数除以余数,依此类推,直到余数为 0。最后一个非零余数就是最大公约数。如果它不是 1,则不存在逆元。
- 将 1 表示为线性组合。 通过回代(back-substitution),或在计算过程中同时跟踪系数,写出 \(1 = a \cdot x + m \cdot y\)。这就是贝祖恒等式(Bézout identity)。
- 化简 x。 取 \(x \bmod m\)。如果 x 为负数,则加上 m(必要时重复),使其落在 0 到 m − 1 的范围内。
实例:a = 7,m = 40。
| 步骤 | 除法 | 商 q | 余数 |
|---|---|---|---|
| 1 | 40 = 5·7 + 5 | 5 | 5 |
| 2 | 7 = 1·5 + 2 | 1 | 2 |
| 3 | 5 = 2·2 + 1 | 2 | 1 |
| 4 | 2 = 2·1 + 0 | 2 | 0 |
最后一个非零余数是 1,因此 \(\gcd(7, 40) = 1\),逆元存在。
回代:
$$1 = 5 - 2\cdot 2 = 5 - 2(7 - 5) = 3\cdot 5 - 2\cdot 7 = 3(40 - 5\cdot 7) - 2\cdot 7 = 3\cdot 40 - 17\cdot 7$$
所以 \(7 \cdot (-17) + 40 \cdot 3 = 1\),由此得 \(x = -17\)。
迭代验算(a 的系数 t): 取 \(t_0 = 0\)(对应 m = 40)和 \(t_1 = 1\)(对应 a = 7),然后使用 \(t_{k+1} = t_{k-1} - q_k \, t_k\)。
| 余数 | 所用商 q | t |
|---|---|---|
| 40 | – | 0 |
| 7 | – | 1 |
| 5 | 5 | 0 − 5·1 = −5 |
| 2 | 1 | 1 − 1·(−5) = 6 |
| 1 | 2 | −5 − 2·6 = −17 |
余数达到 1 的那一行给出 \(t = -17\)。化简:\(-17 + 40 = \)23。
验证: \(7 \cdot 23 = 161 = 4 \cdot 40 + 1\),所以 \(161 \bmod 40 = 1\)。✓
同样的方法也适用于更大的数。对于 a = 17,m = 3120,得到 x = 2753,因为 \(17 \cdot 2753 = 46801 = 15 \cdot 3120 + 1\)。这一组数是教科书中经典的 RSA 示例。
示例输入及其逆元
下面每个逆元都满足 \((a \cdot x) \bmod m = 1\)。当 \(\gcd(a, m) > 1\) 时,不存在逆元。
| a | m | gcd(a, m)(最大公约数) | 逆元 x | 验算 |
|---|---|---|---|---|
| 3 | 11 | 1 | 4 | 3·4 = 12 = 1·11 + 1 |
| 7 | 26 | 1 | 15 | 7·15 = 105 = 4·26 + 1 |
| 5 | 12 | 1 | 5 | 5·5 = 25 = 2·12 + 1 |
| 10 | 17 | 1 | 12 | 10·12 = 120 = 7·17 + 1 |
| 17 | 3120 | 1 | 2753 | 17·2753 = 46801 = 15·3120 + 1 |
| 4 | 6 | 2 | 无 | 4x mod 6 总是偶数,永远不等于 1 |
| 6 | 9 | 3 | 无 | 6x mod 9 总是 3 的倍数,永远不等于 1 |
注意 5 模 12 的逆元就是它自己。一般地,\(x^2 \equiv 1 \pmod{m}\) 除了 1 之外还有其他解,因此有些数是自身的逆元。
关键术语:互素、最大公约数、同余和剩余类
- 模数(m): 数值绕回的正整数,就像钟面一样。
- 同余(≡): \(a \equiv b \pmod{m}\) 表示 m 整除 \(a - b\),因此 a 和 b 除以 m 后余数相同。
- GCD: 最大公约数,即同时整除两个数的最大整数。
- 互素(coprime,即互质): 最大公约数为 1 的两个整数。这正是模逆元存在的充要条件。
- 贝祖恒等式(Bézout identity): 对于整数 a 和 m,存在整数 x 和 y 使得 \(a \cdot x + m \cdot y = \gcd(a, m)\)。当最大公约数为 1 时,对该等式取模 m 得到 \(a \cdot x \equiv 1\),因此 x 就是逆元。
- 剩余类: 模 m 时余数相同的所有整数组成的集合。逆元作为剩余类是唯一的,计算器给出的是 0 到 m − 1 之间的代表元。
- 模乘法逆元: 满足 \(a \cdot x \equiv 1 \pmod{m}\) 的剩余 \(x = a^{-1} \bmod m\)。
欧拉定理: 若 \(\gcd(a, m) = 1\),则 \(a^{\varphi(m)} \equiv 1 \pmod{m}\),其中 \(\varphi\) 是欧拉函数(Euler's totient function)。因此逆元也可以计算为 \(a^{\varphi(m)-1} \bmod m\)。
费马小定理: 当 m = p 为素数时,\(\varphi(p) = p - 1\),因此对于任何不被 p 整除的 a,有 \(a^{-1} \equiv a^{p-2} \pmod{p}\)。例如:\(3^{9} = 19683 = 1789 \cdot 11 + 4\),所以 \(3^{-1} \equiv 4 \pmod{11}\),与上表一致。幂次公式需要知道 m 的因数分解(以求出 \(\varphi\)),而扩展欧几里得算法不需要,因此对于一般模数通常是更快的方法。
常见问题
什么情况下逆元不存在? 当 a 与 m 存在大于 1 的公因数时——例如 4 关于模 6(gcd = 2)就没有逆元。
m 必须是质数吗? 不必。m 可以是任意 ≥ 2 的整数,关键只在于 a 与 m 是否互质。
答案的取值范围是多少? 逆元以最小非负余数的形式给出,取值介于 0 到 m − 1 之间。