如何计算模逆元？

最有效的方法是扩展欧几里得算法，它可以找到满足 ax + my = gcd(a, m) 的整数 x 和 y。当 gcd(a, m) = 1 时，x 即为模逆元。另外，如果 m 是质数，费马小定理给出 a⁻¹ ≡ a^(m-2) (mod m)。

模逆元何时不存在？

当 gcd(a, m) > 1 时，a (mod m) 的模逆元不存在。例如，6 (mod 9) 的逆元不存在，因为 gcd(6, 9) = 3 ≠ 1。

模逆元的实际用途有哪些？

模逆元是 RSA 加密、Diffie-Hellman 密钥交换、椭圆曲线加密、求解线性同余方程、中国剩余定理计算以及计算模分数的基石。

模乘逆元计算器

Q: 什么是模乘逆元？

整数 a 模 m 的模乘逆元是一个整数 x，使得 a·x ≡ 1 (mod m)。它被记作 a⁻¹ (mod m)，且当且仅当 gcd(a, m) = 1（即 a 和 m 互质）时存在。

使用扩展欧几里得算法计算整数 a 在模 m 下的模乘逆元，包含分步表格、结果验证和时钟可视化。

模乘逆元计算器

Embed 模乘逆元计算器 Widget

模乘逆元计算器

什么是模乘逆元？

整数 a 关于模数 m 的模乘逆元是一个在 [0, m-1] 范围内的整数 x，使得：

\( a \cdot x \equiv 1 \pmod{m} \)

它通常写为 a⁻¹ (mod m)，类似于普通算术中的乘法逆元（即 1/a），但应用于模算术领域。

关键条件： 逆元存在的当且仅当 gcd(a, m) = 1 — 也就是说，a 和 m 必须互质。

计算方法：扩展欧几里得算法

最有效的方法是使用扩展欧几里得算法。它能找到满足裴蜀等式的整数 x 和 y：

\( a \cdot x + m \cdot y = \gcd(a, m) = 1 \)

当 gcd(a, m) = 1 时，对等式两边取模 m 得到 a·x ≡ 1 (mod m)，因此 x 就是模逆元。

示例： 求 3⁻¹ (mod 7)：

扩展最大公约数计算得出：3·(5) + 7·(-2) = 15 − 14 = 1，因此 3⁻¹ ≡ 5 (mod 7)。验证：3 × 5 = 15 = 2×7 + 1 ≡ 1 (mod 7) ✓

在密码学和数学中的应用

🔐

RSA 加密

根据公钥指数 e 求解私钥 d = e⁻¹ (mod φ(n))

📈

Diffie-Hellman

基于模算术中离散对数的密钥交换协议

🇮

仿射密码

解密过程使用 a⁻¹ (mod 26) 来撤销加密密钥

🔢

CRT 与数论

中国剩余定理及求解线性同余方程 ax ≡ b (mod m)

👑

椭圆曲线

ECC 中的点加法公式在计算斜率时需要模逆元

📋

模分数

当 gcd(b, m) = 1 时，将 a/b (mod m) 计算为 a · b⁻¹ (mod m)

常见问题解答

问：为什么逆元并不总是存在？

因为模算术是“循环”的，a 的某些倍数可能永远不会落在 1 mod m 上。这恰好发生在 a 和 m 共享公因数时 — 即 gcd(a, m) > 1。

问：质数模数有计算公式吗？

有的！如果 m 是质数且 a 不是 m 的倍数，费马小定理给出： a⁻¹ ≡ a^m-2 (mod m)。这在算法竞赛中经常被使用。

问：结果是唯一的吗？

是的，结果在模 m 下是唯一的。我们始终报告 [0, m-1] 范围内的规范结果。对于任何整数 k，x + km 也是有效的逆元，但它们在模 m 意义下都是等价的。

问：如果 a 是负数怎么办？

该算法可以处理负整数。内部我们会先计算 a (mod m) 得到一个非负代表值，然后再求其逆元。结果始终在 [0, m-1] 范围内。

引用此内容、页面或工具为：

"模乘逆元计算器" 于 https://MiniWebtool.com/zh-cn/模乘逆元计算器/，来自 MiniWebtool，https://MiniWebtool.com/

由 miniwebtool 团队。更新日期：2026年2月18日

您还可以尝试我们的 AI数学解题器 GPT，通过自然语言问答解决您的数学问题。

模乘逆元计算器

模乘逆元计算器

什么是模乘逆元？

计算方法：扩展欧几里得算法

在密码学和数学中的应用

常见问题解答

进阶数学计算:

常用工具: