# 扩展欧几里得算法（ax + by = gcd(a, b)） 对任意符号的整数 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/extended-euclidean-algorithm - **分类:** Math & Numbers - **关键词:** 扩展欧几里得, 贝祖等式, 贝祖系数, 最大公约数, 丢番图方程, 线性丢番图, 数论, 回代 ## 概述 扩展欧几里得算法工具可快速计算任意整数 a 和 b 的最大公约数（gcd）、最小公倍数（lcm）以及贝祖等式（Bézout identity）系数，支持输出每一步带前向线性表示的完整除法过程。此外，通过填入常数 c，工具可直接求解形如 ax + by = c 的二元一次线性丢番图方程，输出特解与参数化通解或明确报告无整数解。 ## 输入项 - **数值 a** (text): First integer; negative values are supported. - **数值 b** (text): Second integer; negative values are supported. - **右端 c（可选，解 ax + by = c）** (text): Optional target: solves ax + by = c when gcd(a, b) divides c. - **输出样式** (select) ## 适用场景 - 需要推导贝祖等式 a·x + b·y = gcd(a, b) 中的整数系数 x 与 y 时。 - 求解二元一次线性丢番图方程 ax + by = c 的整数特解与参数化通解时。 - 学习或验证初等数论、模逆元计算及欧几里得辗转相除法的逐步计算过程时。 ## 工作原理 - 输入两个整数 a 和 b，系统运行扩展辗转相除法追踪每一步的商与余数。 - 算法在前向除法中同步递推维护系数序列，使每个余数 r 均满足 r = a·s + b·t，直到余数为 0 锁定 gcd 与 Bézout 等式。 - 若填入常数 c，系统检验 gcd(a, b) 是否整除 c，若整除则等比缩放求出特解并构造包含步长 (b/gcd)·t 与 (a/gcd)·t 的通解公式。 - 根据所选输出样式，生成简洁结果验证或包含完整每步商数 q 与线性关系的除法步骤表。 ## 使用案例 - 密码学与数论教学：演示 RSA 算法密钥生成中模反元素及辗转相除步骤。 - 离散数学作业验证：逐步核对 Bézout 恒等式推导过程与计算结果。 - 工程配比与硬币兑换问题建模：求解离散步长约束下的线性丢番图整数解。 ## 常见问题 ### 输入负整数时工具能正常求解吗？ 可以。工具完全支持负整数输入，最大公约数 gcd 始终保持非负，递推出的 Bézout 系数满足等式恒成立。 ### 线性丢番图方程什么时候会出现无整数解？ 当且仅当常数 c 无法被 a 和 b 的最大公约数 gcd(a, b) 整除时，该方程不存在任何整数解，工具会明确提示。 ### “显示除法步骤”与“结果与验证”有什么区别？ “显示除法步骤”会完整打印辗转相除中每一步的余数 r、商 q 及线性组合 r = a·s + b·t；“结果与验证”则仅输出最终 gcd、等式与方程通解。 ### 该工具能用于求解模逆元吗？ 可以。求解 a 模 m 的逆元等价于求解 ax + my = 1。当 gcd(a, m) = 1 时，所得的 x 即为对应模逆元的基底。 ### 通解公式中的参数 t 代表什么？ 参数 t 代表任意整数（t ∈ ℤ），改变 t 的取值可以遍历丢番图方程的所有有效整数解对 (x, y)。 ## 相关工具 - [布尔代数表达式化简器（卡诺图辅助）](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 稀释剂。 - [模逆元计算器（扩展欧几里得算法）](https://elysiatools.com/zh/tools/modular-inverse-calculator): 用扩展欧几里得算法求 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/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 图像处理示例，包括图像读取保存、缩放和格式转换