模逆元计算器

整数 a 在模 m 下的乘法逆元是一个整数 x，使 a 与 x 的乘积除以 m 后余数为 1。用同余语言表示，即 a 乘 x 与 1 模 m 同余。本计算器通过扩展欧几里得算法求出最小非负逆元，并显示乘法验证。模数必须是大于一的整数。 当且仅当 a 与 m 互质，即最大公约数为 1 时，逆元才存在。如果它们有更大的公因数，那么涉及 a 的任何乘积在模 m 下仍可被该因数整除，不可能得到余数 1。例如，6 在模 15 下没有逆元，因为它们的最大公约数为 3。相比之下，3 在模 11 下的逆元是 4，因为 3 乘 4 等于 12，除以 11 后余数为 1。 扩展欧几里得算法不仅计算最大公约数，还能求出系数 x 和 y，使 ax 加 my 等于最大公约数。当该公约数为 1 时，将 x 对 m 取模即可得到模逆元。如果 x 为负数，加上足够多个 m，就能将其调整到零至 m 减一的标准范围，同时不改变其同余类。 模逆元在模运算中取代除法。不能直接对剩余类使用普通除法，因为不同整数可以代表同一个余数。在模 m 下除以 a，意味着乘以 a 的逆元，前提是该逆元存在。这种方法是解线性同余方程、化简模分式、应用中国剩余定理及推导许多数论算法的核心。 密码学广泛使用模逆元。RSA 密钥生成会对与欧拉函数相关的数值求指数的逆元；椭圆曲线计算在有限域上求点运算公式时也会用到逆元。编码理论、校验和、伪随机数生成器和计算机代数同样依赖高效的逆元计算。实际密码学实现使用精心设计的大整数及恒定时间算法，而非浏览器的普通数值运算，但底层数论原理相同。 逆元是在模 m 的意义下唯一，而不是作为普通整数唯一。如果 4 是 3 在模 11 下的逆元，那么 15、负 7，以及任何与 4 相差 11 的整数倍的数，都表示同一个逆元剩余类。计算器报告 4，因为最小非负代表元最便于比较和复用。 验证结果时，将原整数乘以显示的逆元，再除以模数，检查余数是否为 1。负数输入也适用同样规则，因为余数总能规范到标准范围。若工具提示逆元不存在，可另行计算最大公约数；任何大于 1 的结果都说明存在障碍。