免费乘法逆模计算器

介绍乘法逆模计算器

在数论以及密码学、随机数生成和编程竞赛等实际应用中，经常需要求模逆（模乘法逆元）。逆模计算器自动完成此任务：对于给定的底数$a$和模数$m$，确定整数$x$使得$a \times x \equiv 1 \pmod{m}$。这一免费在线模逆查找器在底层使用扩展欧几里得算法，即使$m$很大也能在毫秒级给出答案。

计算器的界面简单直观。您提供模数$m$（正整数）和整数$a$，工具计算$\gcd(a, m)$。如果最大公约数为1，则返回区间$\{1, 2, \dots, m-1\}$内的唯一逆元；否则报告不存在逆元。该行为基于下文解释的数学条件。

什么是模逆？

正式地，如果整数$x$满足

$$a \times x \equiv 1 \pmod{m}.$$

则称$x$为$a$模$m$的模逆。另一种表述是：$a \times x$除以$m$的余数必须恰好为$1$。例如，考虑$a = 3$和$m = 7$；逆元是$5$，因为$3 \times 5 = 15$且$15 \bmod 7 = 1$。

任何解$x$都可以加上$m$的整数倍：如果$x$是一个逆元，则$x + k m$（对任意整数$k$）也满足同余式。因此计算器返回集合$\{1, 2, \dots, m-1\}$中的规范代表，该集合内逆元是唯一的。

逆元何时存在？

模逆的存在完全取决于$a$与$m$的关系：

• 存在逆元当且仅当$\gcd(a, m) = 1$，即$a$与$m$互质（互素）。
• 不存在逆元当$\gcd(a, m) > 1$。

当$m$为素数时，每个不为$m$倍数的非零整数$a$自动满足$\gcd(a, m) = 1$，因此都有逆元。对于合数模，一个简单例子可以说明不成立：取$a = 3$和$m = 6$。由于$\gcd(3, 6) = 3$，没有整数$x$能使$3x \equiv 1 \pmod{6}$。检查$x = 1, 2, 3, 4, 5$对应的余数$3, 0, 3, 0, 3$，确认永远不会出现$1$。

如何使用模逆计算器

步骤非常简单：

1. 输入模数 $m$（正整数）。
2. 输入整数 $a$。
3. 点击计算按钮。

工具首先计算 $\gcd(a, m)$。如果最大公约数为1，则运行扩展欧几里得算法求逆元，并显示结果以及步骤的简要说明。如果两数不互质，计算器会告知逆元不存在。

由于算法运行时间为 $O(\log m)$，即使模数有几十位数字，也能几乎瞬间处理完毕。

贝祖等式与扩展欧几里得算法

计算模逆最有效的方法是扩展欧几里得算法。该算法求解贝祖等式：

$$a x + m y = \gcd(a, m).$$

当$a$与$m$互质时，$\gcd(a, m) = 1$，等式变为

$$a x + m y = 1.$$

将整个方程对$m$取模，消去$m y$项（它是$m$的倍数），得到

$$a x \equiv 1 \pmod{m}.$$

因此算法得到的系数$x$正是模逆。

一个示例

求 $7$ 模 $19$ 的逆元。应用扩展欧几里得算法：

$$19 = 2 \times 7 + 5,$$ $$7 = 1 \times 5 + 2,$$ $$5 = 2 \times 2 + 1.$$

回代得到 $1 = 3 \times 19 - 8 \times 7$。模 $19$ 化简得 $-8 \times 7 \equiv 1 \pmod{19}$；将负系数加上 $19$ 转化为正余数，得到 $11$。因此 $11$ 是逆元，因为 $7 \times 11 = 77 \equiv 1 \pmod{19}$。

小模数的暴力枚举方法

如果模数很小，可以通过尝试法求逆元：测试每个整数 $x = 1, 2, \dots, m-1$ 直到 $a x \bmod m = 1$。虽然暴力方法容易理解，但当 $m$ 增大时变得不可行，这就是专业工具和编程库都采用扩展欧几里得算法的原因。

为什么模逆很重要

快速计算模逆的能力在多个领域至关重要：

• 密码学：在 RSA 中，解密指数 $d$ 是加密指数 $e$ 模 $\phi(n)$ 的模逆。
• 编程：许多竞赛编程问题和库需要模除法，而模除法是通过乘以逆元来实现的。
• 数学：求解线性同余方程以及构造有限域都依赖于逆元的存在和高效计算。