模乘法逆元计算器

输入计算

整数 a

模数 m

结果

乘法逆元

4

a^-1 mod m

gcd(a, m)	1
逆元存在	是

什么是模 m 下的乘法逆元？

整数 a 关于模 m 的模乘法逆元，是一个介于 1 到 m−1 之间的整数 x，使得 \((a \cdot x) \bmod m = 1\)。换句话说，把 a 乘以 x 后再除以 m，余数恰好为 1。它相当于在模运算中实现"除以 a"的操作，是数论和密码学的基石之一——广泛应用于 RSA 密钥生成、哈希运算、中国剩余定理等场景。

Modular arithmetic wraps the number line into a circle of m positions.

如何使用本计算器

输入整数 a 和模数 m（m 必须大于或等于 2）。计算器会先对 a 取模 m，再运行扩展欧几里得算法，若逆元存在则返回结果。即使 a 为负数也无需担心，系统会自动将其归约到 0 到 m−1 的区间内。

公式原理详解

逆元存在当且仅当 \(\gcd(a, m) = 1\)——也就是说，a 与 m 除了 1 之外没有其他公因数（两者互质）。 $$\text{a} \cdot x \equiv 1 \pmod{\text{m}}, \quad x \text{ exists } \iff \gcd\!\left(\text{a},\, \text{m}\right) = 1$$ 扩展欧几里得算法可以找到满足 \(a \cdot s + m \cdot t = \gcd(a, m)\) 的整数 s 和 t。当最大公约数为 1 时，把系数 s 对 m 取模，得到的结果就是逆元；若 \(\gcd(a, m) \neq 1\)，则逆元不存在。

The extended Euclidean algorithm yields x satisfying a·x + m·y = 1.

实例演算

求 3 关于模 11 的逆元。我们需要找到满足 \((3 \cdot x) \bmod 11 = 1\) 的 x。逐一尝试可知，\(3 \cdot 4 = 12\)，而 \(12 \bmod 11 = 1\)，因此逆元就是 4。由于 \(\gcd(3, 11) = 1\)，扩展欧几里得算法能瞬间给出同样的结果。

Multiplying a by its inverse x lands exactly on 1 after wrapping mod m.

常见问题

什么情况下逆元不存在？当 a 与 m 不互质时。例如，4 在模 8 下没有逆元，因为 \(\gcd(4, 8) = 4 \neq 1\)。

模数必须是质数吗？不必。只要 a 与模数互质，任何模数都可以。如果 m 是质数，那么 1 到 m−1 之间的每一个非零的 a 都有逆元。

为什么结果总是落在 1 到 m−1 之间？因为我们会把逆元对 m 取模，得到的是最小正余数这一标准（规范）表示。