免费模逆计算器

模逆计算器是一款免费在线工具，可同时处理乘法逆元和加法逆元。无论您是需要用于密码学作业的模乘法逆元，还是数论问题的加法逆元，该计算器都能通过扩展欧几里得算法快速得出结果。它完全免费，服务于所有从事模运算工作的学生、教育工作者和专业人士。

模同余——基础

在定义模逆之前，必须理解同余的概念。设 $n$ 为非零自然数。如果两个整数 $a$ 和 $b$ 除以 $n$ 后余数相同，则称它们模 $n$ 同余。等价地，差值 $a-b$ 是 $n$ 的倍数。该关系表示为：

$$a \equiv b \pmod{n}.$$

以下两个例子可以澄清这一概念：

• 例 1： $14$ 和 $99$ 模 $5$ 同余，因为 $99-14 = 85$（是 $5$ 的倍数）。两数除以 $5$ 的余数均为 $4$。 $14 \equiv 99 \pmod{5}$。

• 例 2： $14$ 和 $99$ 模 $7$ 不同余，因为 $85$ 不是 $7$ 的倍数。它们的余数分别为 $0$ 和 $1$。 $14 \not\equiv 99 \pmod{7}$。

扎实掌握同余概念对于处理模逆至关重要。

加法逆元

对于加法，单位元是 $0$。如果整数 $x$ 满足 $a + x \equiv 0 \pmod{m}$，则称 $x$ 为 $a$ 模 $m$ 的 加法逆元。

加法逆元始终存在。手动求法：从 $-a$ 开始，反复加或减 $m$，直到结果落在集合 $\{0,1,\dots,m-1\}$ 中。

例 1： 求 $4$ 模 $30$ 的加法逆元。 形如 $-4 + 30k$ 的数为 $\dots, -4, 26, 56, \dots$。 介于 $0$ 到 $29$ 之间的数值是 $26$。 因此 $-4 \equiv 26 \pmod{30}$。

例 2： 求 $44$ 模 $13$ 的加法逆元。 序列 $-44 + 13k$ 给出 $\dots, -44, -31, -18, -5, 8, 22, \dots$。 落在 $\{0,\dots,12\}$ 内的结果是 $8$。

乘法逆元

对于乘法，单位元是 $1$。当整数 $x$ 满足 $a \times x \equiv 1 \pmod{m}$ 时，称 $x$ 为 $a$ 模 $m$ 的 乘法逆元（或模乘法逆元）。

不同于加法逆元，乘法逆元 不 总是存在。它存在的条件是 $a$ 和 $m$ 互质（最大公约数为 $1$）。例如，$2$ 模 $6$ 没有乘法逆元，因为对于每个 $x \in \{1,2,3,4,5\}$，乘积 $2x \bmod 6$ 都不等于 $1$。

乘法逆元广泛应用于密码学，最著名的是 RSA 算法，用于保护敏感数据。

计算乘法逆元的三种方法

存在多种方法，选择取决于模数大小和可用工具。

暴力（朴素）方法

尝试 $\{1,\dots,m-1\}$ 中的每个 $x$，直到 $a \times x \bmod m = 1$。该方法适用于小模数，但对于大数不实用。

扩展欧几里得算法

Bézout 恒等式指出，对于任意整数 $a$ 和 $m$，存在整数 $x$ 和 $y$，使得

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

如果 $\gcd(a,m)=1$（这是乘法逆元存在的条件），则等式变为 $a x + m y = 1$。两边模 $m$ 化简得

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

因此从扩展欧几里得算法得到的系数 $x$ 即为所需的乘法逆元。该方法高效，适用于任意模数，也是模逆计算器所采用的算法。

费马小定理

当模数 $m$ 为质数且 $a$ 不是 $m$ 的倍数时，费马小定理表明

$$a^{m-1} \equiv 1 \pmod{m}.$$

两边同时除以 $a$（因为 $a$ 在模质数下可逆）得到

$$a^{m-2} \equiv a^{-1} \pmod{m}.$$

因此 $a^{m-2} \bmod m$ 即为乘法逆元。该方法很快，但仅适用于质数模数。

如何使用免费模逆计算器

使用此在线模逆计算器很简单：

1. 选择所需的逆元类型：乘法或加法。
2. 输入整数 $a$ 和模数 $m$。
3. 点击计算按钮。

工具立即返回标准范围 $\{0,1,\dots,m-1\}$ 内的模逆（对于乘法逆元，排除了 $0$，因为 $0$ 没有乘法逆元）。还显示计算过程的简要说明，帮助您理解结果如何得出。

无论您是学习同余关系、实现加密算法，还是只需快速计算，这款免费在线模逆计算器都能提供可靠高效的解决方案。