模逆元计算工具
计算整数在模数下的模逆元，展示扩展欧几里得算法的详细计算步骤。
计算整数 a 在模 m 下的逆元，即求 x 使得 a × x ≡ 1 (mod m)
计算历史
工具使用说明
基本操作
- 在输入框中输入整数 a 和模数 m
- 点击"计算模逆元"按钮或按Enter键进行计算
- 点击"清空"按钮清除当前输入
复制功能
- 点击"复制结果"按钮复制模逆元值
- 点击"复制过程"按钮复制计算过程
- 在历史记录中，可以复制特定历史项的结果
- 复制成功会有提示信息显示
历史记录
- 每次计算都会自动保存到历史记录
- 点击历史记录项可快速重新计算
- 点击历史记录项的复制按钮可复制结果
- 最多保存10条最近的计算记录
- 可点击"清除历史记录"清空所有历史
使用技巧
- 尝试输入不同的数字组合观察模逆元的特性
- 比较质数模数和非质数模数下的模逆元计算
- 使用历史记录功能快速切换不同数字组合
- 参考计算步骤理解扩展欧几里得算法的原理
注意事项
- 模数 m 必须大于1
- 整数 a 和模数 m 必须互质（gcd(a, m) = 1）
- 如果 a 和 m 不互质，则模逆元不存在
- 模逆元的结果在 0 到 m-1 之间
- 历史记录保存在浏览器本地存储中
模逆元说明
模逆元（Modular Multiplicative Inverse）是指对于整数 a 和模数 m，存在一个整数 x 使得 a × x ≡ 1 (mod m)。
例如：3 在模 11 下的逆元是 4，因为 3 × 4 = 12 ≡ 1 (mod 11)。
计算方法：
- 扩展欧几里得算法：求解 ax + my = 1 的整数解 x
- 费马小定理：当 m 是质数时，a^(m-2) mod m 就是 a 的模逆元
- 枚举法：从 1 到 m-1 枚举 x，检查是否满足 a × x ≡ 1 (mod m)
示例：
计算 3 在模 11 下的逆元：
- 我们需要找到 x 使得 3 × x ≡ 1 (mod 11)
- 尝试 x = 1: 3 × 1 = 3 ≡ 3 (mod 11) ≠ 1
- 尝试 x = 2: 3 × 2 = 6 ≡ 6 (mod 11) ≠ 1
- 尝试 x = 3: 3 × 3 = 9 ≡ 9 (mod 11) ≠ 1
- 尝试 x = 4: 3 × 4 = 12 ≡ 1 (mod 11) ✓
- 所以 3 在模 11 下的逆元是 4
使用扩展欧几里得算法计算 3 在模 11 下的逆元：
- 求解 3x + 11y = 1
- 11 = 3 × 3 + 2
- 3 = 2 × 1 + 1
- 2 = 1 × 2 + 0
- 回代：1 = 3 - 2 × 1 = 3 - (11 - 3 × 3) × 1 = 3 × 4 - 11 × 1
- 所以 x = 4，即逆元为 4
应用领域：
- 密码学：RSA加密算法、椭圆曲线密码等
- 编码理论：纠错码、循环码等
- 计算机科学：哈希函数、随机数生成等
- 数学：同余方程求解、数论问题等