什么是模乘法逆元计算器？
这个计算器用于求整数 a 关于模 m 的模乘法逆元，也就是在 \(0 \le x < m\) 范围内唯一满足 \(a \cdot x \equiv 1 \pmod{m}\) 的整数 x。它采用扩展欧几里得算法，同时还能算出 a 与 m 的最大公约数 \(\gcd(a, m)\)。这属于纯粹的数论运算，在世界各地的计算结果完全一致；它在密码学（如 RSA 密钥生成）、哈希算法以及求解一次同余方程中都有广泛应用。
如何使用
输入整数 a 和一个正的模数 m（建议取 \(m \ge 2\)，这样才能得到有意义且唯一的逆元）。工具会先把 a 对 m 取模，再运行扩展欧几里得算法，最终给出逆元以及 \(\gcd(a, m)\)。如果 a 与 m 不互质（\(\gcd \ne 1\)），则逆元不存在，计算器会给出相应提示。
公式解析
当且仅当 \(\gcd(a, m) = 1\) 时，逆元才存在。扩展欧几里得算法会找到一对整数 s 和 t，使得 \(a \cdot s + m \cdot t = \gcd(a, m)\)。当 gcd 为 1 时，便有 \(a \cdot s \equiv 1 \pmod{m}\)，因此逆元为
$$x = ((s \bmod m) + m) \bmod m$$并将其化为最小的非负余数。
实例演示
设 \(a = 7\)，\(m = 4\)：由于 \(7 \equiv 3 \pmod{4}\)，问题转化为求解 \(3x \equiv 1 \pmod{4}\)。对 \((7, 4)\) 运行扩展欧几里得算法，得到 \(\gcd = 1\) 及贝祖系数 \(s = -1\)，于是
$$x = ((-1 \bmod 4) + 4) \bmod 4 = 3$$验证：\(7 \cdot 3 = 21 = 5 \cdot 4 + 1 \equiv 1 \pmod{4}\)。所以答案为 3。
常见问题
什么情况下逆元不存在？只有当 \(\gcd(a, m) > 1\) 时才不存在。例如 \(a = 6\)，\(m = 9\)，它们的 \(\gcd = 3\)，因此不存在逆元。
a 可以是负数或大于 m 吗？可以。我们会先对 a 取模 m；由于 \(a \equiv a' \pmod{m}\)，所以结果不会改变。
如果 m = 1 会怎样？任何整数对 1 取模都等于 0，因此逆元自然就是 0。
