模逆元计算器

模逆元计算器

增长中 AI Skill PRO

输入计算

结果

模逆元
2,753
满足 (a·x) mod m = 1 的 x
逆元存在 是
gcd(a, m) 1

数学公式

a·x≡1(modm)⟹x=a−1modm\text{a} \cdot x \equiv 1 \pmod{\text{m}} \quad\Longrightarrow\quad x = \text{a}^{-1} \bmod \text{m}
使用统计

广告

报告本页错误

什么是模逆元?

整数 a 关于模数 m 的模乘法逆元,是指满足 \((a \cdot x) \bmod m = 1\) 的整数 x。它相当于模运算中的"除法"运算,在数论、RSA 加密体制以及众多编码理论算法中都扮演着核心角色。本计算器利用扩展欧几里得算法来求出 x。

数轴环绕着钟表般的圆形模数环,显示 a 乘 x 落在 1 上
模逆元 x 与 a 相乘后将 a 映回 1,在模 m 上循环回绕。

如何使用本计算器

输入数字 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 将其归一化为正值。

广告
扩展欧几里得算法步骤的扁平流程图,生成最大公约数和系数
扩展欧几里得算法给出系数,当 gcd(a, m) = 1 时即得逆元。

实例演算

求 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\) 时它才存在。扩展欧几里得算法分三步求出它。

  1. 反复相除。 用 m 除以 a,再用上一步的除数除以余数,依此类推,直到余数为 0。最后一个非零余数就是最大公约数。如果它不是 1,则不存在逆元。
  2. 将 1 表示为线性组合。 通过回代(back-substitution),或在计算过程中同时跟踪系数,写出 \(1 = a \cdot x + m \cdot y\)。这就是贝祖恒等式(Bézout identity)。
  3. 化简 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 之间。

最后更新:

数学和统计热门计算器

查看全部数学和统计计算器