# 模逆元计算器（扩展欧几里得算法）

用扩展欧几里得算法求 a⁻¹ mod m：给出 Bézout 系数 a·x + m·y = gcd(a, m) 与完整的前向系数表（每行满足 r = a·s + m·t），并用 a × a⁻¹ ≡ 1 (mod m) 回代验证。支持 RSA 量级的大数（可达 10⁵¹² 位数级输入）；gcd(a, m) ≠ 1 时明确报告逆元不存在。经典例：RSA 中 17⁻¹ mod 3120 = 2753。

> 标准页面: https://elysiatools.com/zh/tools/modular-inverse-calculator

- **分类:** Math & Numbers

- **关键词:** 模逆元, 扩展欧几里得, 贝祖等式, 贝祖系数, rsa, 丢番图方程, 模运算, 数论, 乘法逆元

## 概述

模逆元计算器利用扩展欧几里得算法快速求解 a⁻¹ mod m，并输出 Bézout 等式系数与完整递推推导步骤。工具支持 RSA 级别的大数运算（最高可达 10⁵¹² 位），能自动检验最大公约数 gcd(a, m)，在逆元不存在时给出明确提示，并通过回代等式验证计算结果的准确性。

## 输入项

- **数值 a** (text): The value to invert; negative values are reduced mod m first.
- **模数 m** (text): Modulus, m ≥ 2. Inputs up to 10⁵¹² are accepted (RSA-sized).
- **输出样式** (select)

## 适用场景

- 在 RSA 密码学中根据公钥指数 e 和欧拉函数 φ(n) 计算私钥解密指数 d 时。
- 求解数论与离散数学作业中的同余方程 ax ≡ b (mod m) 及 Bézout 线性等式系数时。
- 设计或破解经典密码（如仿射密码）时计算乘法密钥在模运算下的逆元时。

## 工作原理

- 输入底数 a 和模数 m（m ≥ 2，若 a 为负数会自动先对其取模化简）。
- 选择输出样式为“结果与验证”或“显示扩展欧几里得步骤”。
- 算法执行扩展欧几里得递推，计算 gcd(a, m) 并求解 Bézout 恒等式 a·x + m·y = gcd(a, m)。
- 若 gcd(a, m) = 1 则输出最小正整数模逆元并给出 a × a⁻¹ ≡ 1 (mod m) 验证式；若最大公约数不为 1 则提示逆元不存在。

## 使用案例

- 密码学研究人员与工程师进行 RSA 密钥对生成和解密指数 d 的验证推导。
- 高校学生与教师在学习离散数学和初等数论时核对扩展欧几里得步骤表。
- 网络安全 CTF 选手快速分析同余方程并解密仿射密码或模同余密文。

## 常见问题

### 什么时候 a 存在模 m 的逆元？

当且仅当 a 与模数 m 互质（即 gcd(a, m) = 1）时，模逆元才存在。

### 如果输入的 a 是负数，工具如何处理？

工具会自动先将负数 a 对 m 进行模运算化简为正整数，然后再求解逆元。

### 什么是 Bézout（贝祖）等式？

它是形如 a·x + m·y = gcd(a, m) 的线性等式，其中整数 x 在模 m 下即对应 a 的乘法逆元。

### 该计算器支持的最大数值是多少？

支持大整数运算，可处理高达 10⁵¹² 位数级别的 RSA 超大模数和数值。

### 为什么有些情况下计算器提示“逆元不存在”？

因为输入的 a 与模数 m 存在大于 1 的公约数，无法通过模乘法得到余数 1。

## 相关工具

- [布尔代数表达式化简器（卡诺图辅助）](https://elysiatools.com/zh/tools/boolean-algebra-simplifier): 化简布尔函数并给出最小与或式（SOP）：输入表达式（A–D，+ 或 · 与、' 非，≤4 个变量）或直接给最小项 Σm 列表；用 Quine-McCluskey 算法求全部素蕴涵项，先取必要素蕴涵项再做精确最小覆盖，输出最小 SOP、格雷码卡诺图（2–4 变量）、Σm 规范式，并在全部赋值上验证与原函数一致。经典例：AB + A'B → B；Σm(0,1,2,4,5,6)（3 变量）→ B' + C'。
- [稀释比换算器（1:X ↔ 1/X ↔ 百分比）](https://elysiatools.com/zh/tools/dilution-ratio-converter): 在实验室稀释的各色写法之间互换：比例 1:X、分数 1/X、百分比浓度，并换算稀释倍数与溶质/稀释剂份数。支持两种 1:X 约定（X 为总份数，或 1 份溶质加 X 份稀释剂），输入最终体积即可算出溶质与稀释剂的取用量。经典示例：1:5 = 1/5 = 20%，配 100 mL 取 20 mL 原液加 80 mL 稀释剂。
- [扩展欧几里得算法（ax + by = gcd(a, b)）](https://elysiatools.com/zh/tools/extended-euclidean-algorithm): 对任意符号的整数 a、b 求解 Bézout 等式 a·x + b·y = gcd(a, b)：给出完整的前向除法步骤表（每行满足 r = a·s + b·t）、gcd 与 lcm。填入可选的右端 c 即变身为线性丢番图方程求解器：gcd | c 时给出特解与通解 x = x₀ + (b/g)t，否则明确报告无整数解。经典例：240 × (−9) + 46 × 47 = 2。
- [模运算计算器（加减乘 / 逆元 / 快速幂）](https://elysiatools.com/zh/tools/modulo-arithmetic-converter): 在模 m 下做加、减、乘、逆元与快速幂运算，全部使用 BigInt 精确计算（数值可达 10¹⁸）。加、减、乘给出逐步约简过程并输出 \[0, m−1\] 上的规范代表；逆元用扩展欧几里得算法求 a⁻¹ mod m，gcd(a, m) ≠ 1 时明确报告不存在；快速幂展示平方-乘法表中指数二进制分解的每个数位。经典例：17⁵ mod 13 = 10；5⁻¹ mod 18 = 11。
- [真值表生成器](https://elysiatools.com/zh/tools/truth-table-generator): 生成布尔表达式的完整真值表（最多 6 个变量，64 行）：支持 + 或、^ 异或、·/*/& 或连写与、!/~/' 非、括号；按字母序列出变量，逐行列出赋值与函数值 F，并给出规范式 Σm（最小项）与 ΠM（最大项）。经典例：AB + A'C 的 ON-set 为 Σm(1,3,6,7)；A ^ B ^ C 为奇校验函数 Σm(1,2,4,7)。
- [角速度单位换算器（rad/s / rpm / deg/s / Hz）](https://elysiatools.com/zh/tools/angular-velocity-converter): 角速度/角频率单位互转：rad/s（SI 基准）↔ rpm（转每分，1=2π/60 rad/s）↔ deg/s（度每秒，1=π/180 rad/s）↔ Hz（转每秒，1=2π rad/s）。注意 Hz 用于角频率时指每秒一整圈，故 1 Hz=2π rad/s。经 rad/s 中转后输出目标单位，并列出全部四单位等值。参考：黑胶 33⅓ rpm≈3.49 rad/s、发动机怠速 ~800 rpm≈83.8 rad/s。
- [风管截面尺寸计算器（按风量与流速）](https://elysiatools.com/zh/tools/duct-size-calculator): 由风量 Q 与设计流速 v 求风管截面尺寸：截面积 A=Q/v。圆形风管直径 D=√(4A/π)；矩形风管给定长宽比 r=a/b，则 b=√(A/r)，a=r·b，并按 ASHRAE 给出等效直径 D_eq=1.30·(a·b)^0.625/(a+b)^0.25。风量支持 m³/s/m³/h/CFM，结果同时给出 mm 与英寸。
- [疲劳极限计算器（Goodman / Gerber / Soderberg）](https://elysiatools.com/zh/tools/fatigue-limit-calculator): 平均应力修正下的疲劳安全系数。给定应力幅 σ_a、平均应力 σ_m，以及材料 σ_uts、疲劳极限 σ_-1、屈服 σ_y，输出三种经典判据的安全系数：Modified Goodman（线性保守）、Gerber（抛物线，更贴合延性材料）、Soderberg（用 σ_y，最保守）。取三者最小值为控制值，并判定工作点是否在 Haigh 图 Goodman 线内侧。

## 示例

- [Web Python 图像处理示例](https://elysiatools.com/zh/samples/web-image-processing-python): Web Python 图像处理示例，使用 PIL/Pillow 包括读取、保存、缩放和格式转换
- [Android Java 图像处理示例](https://elysiatools.com/zh/samples/android-image-processing-java): Android Java 图像处理示例，包括图像读取保存、缩放和格式转换
- [Android Kotlin 图像处理示例](https://elysiatools.com/zh/samples/android-image-processing-kotlin): Android Kotlin 图像处理示例，包括图像读取保存、缩放和格式转换
- [Web Rust 图像处理示例](https://elysiatools.com/zh/samples/web-image-processing-rust): Web Rust 图像处理示例，包括图像读取保存、缩放和格式转换