无需登录 数据私有 本地保存

简单线性丢番图方程求解 - ax+by=c

21
0
0
0

线性丢番图方程求解器

求解二元一次不定方程 ax + by = c 的整数解，基于扩展欧几里得算法

快捷示例： 15x + 21y = 12 7x + 11y = 100 6x + 9y = 14 10x + 25y = 35
输入方程参数
a
请输入整数系数 a
b
请输入整数系数 b
c
请输入整数常数 c

输入方程系数并点击「求解方程」查看结果

支持任意整数，包括负数和零

常见问题与知识点

线性丢番图方程（Linear Diophantine Equation）是形如 ax + by = c 的二元一次不定方程，其中 a、b、c 为整数，要求解 x、y 也是整数。该方程以古希腊数学家丢番图（Diophantus）命名。它是数论中最基础的不定方程之一，在密码学（如RSA）、计算机科学（如线性同余）和组合数学中有广泛应用。

方程 ax + by = c 有整数解的充要条件是：gcd(a, b) 整除 c。也就是说，c 必须是 a 和 b 的最大公约数的倍数。如果 gcd(a, b) ∤ c（即 c 不能被 gcd(a,b) 整除），则方程无整数解。例如：6x + 9y = 14 中 gcd(6,9)=3，但 14 不能被 3 整除，因此无整数解。

扩展欧几里得算法（Extended Euclidean Algorithm）是欧几里得算法的扩展版本，不仅能求出两个整数 a 和 b 的最大公约数 g = gcd(a, b)，还能找到一对整数 (x₀, y₀) 使得 ax₀ + by₀ = g。这被称为贝祖等式（Bézout's identity）。求得 (x₀, y₀) 后，乘以 c/g 即可得到原方程 ax+by=c 的一组特解。算法的时间复杂度为 O(log min(|a|,|b|))，非常高效。

设 g = gcd(a, b)，若 c = g·k，则特解为 (x₀·k, y₀·k)。通解为：
x = x₀·k + (b/g)·t
y = y₀·k − (a/g)·t
其中 t 为任意整数（t ∈ ℤ）。这是因为 (b/g)·t 和 −(a/g)·t 代入后恰好抵消：a·(b/g)·t + b·(−a/g)·t = (ab/g − ab/g)·t = 0。注意 b/g 和 a/g 都是整数，因为 g = gcd(a,b)。

将通解代入不等式 x ≥ 0 和 y ≥ 0，解出参数 t 的整数范围。具体地：
• 由 x₀ + (b/g)·t ≥ 0 得 t 的下界或上界（取决于 b/g 的符号）
• 由 y₀ − (a/g)·t ≥ 0 得 t 的上界或下界（取决于 a/g 的符号）
取交集后，范围内的所有整数 t 对应非负整数解。如果交集为空，则无非负整数解。本工具会自动计算并展示该范围内的解。

应用非常广泛，包括：货币找零问题（用两种面额凑出指定金额）、密码学（RSA算法中的模逆运算依赖扩展欧几里得算法）、化学配平（某些化学反应方程式配平可转化为丢番图方程）、调度问题（两种周期性任务的同步）、整数规划的基础子问题等。理解丢番图方程的求解是学习数论和离散数学的重要基石。
🔧 相关工具