Linear Diophantine Solver: ax + by = c
Enter integer coefficients and this calculator will determine whether integer solutions exist, then show the full parametric solution.
Tip: Works with positive/negative integers and edge cases like a=0 or b=0.
What is a Diophantine equation?
A Diophantine equation is an equation where we only care about integer solutions. In this page, we focus on the classic linear form:
ax + by = c
where a, b, and c are integers, and we want integer values of x and y.
When do integer solutions exist?
The key test is the greatest common divisor (gcd). Let g = gcd(|a|, |b|). Integer solutions exist if and only if g divides c.
- If c % g = 0, solutions exist (in fact, infinitely many in most non-degenerate cases).
- If c % g ≠ 0, there are no integer solutions.
General solution form
Once one particular solution (x₀, y₀) is found, all integer solutions can be written with a parameter t ∈ ℤ:
- x = x₀ + (b/g)t
- y = y₀ - (a/g)t
This is exactly what the calculator computes and displays, along with sample integer pairs for a chosen range of t.
Example walkthrough
Example: 15x + 21y = 12
Compute gcd(15,21)=3. Since 3 divides 12, solutions exist.
One valid particular solution is (x₀, y₀) = (8, -4). Therefore, all solutions are:
- x = 8 + 7t
- y = -4 - 5t
Try entering these values in the calculator above and inspect the sample list for different values of t.
Why this matters in practice
Linear Diophantine equations appear in many practical and theoretical settings:
- Coin and currency combinations
- Resource packing and batching problems
- Modular arithmetic and cryptography foundations
- Scheduling with integer constraints
Important edge cases
1) a = 0
Equation becomes by = c. Then y = c/b must be integer, and x is free.
2) b = 0
Equation becomes ax = c. Then x = c/a must be integer, and y is free.
3) a = b = 0
If c = 0, every integer pair works. If c ≠ 0, no solution exists.
Final note
This tool is designed for quick, exact integer math and clear reasoning. If you need extensions (three variables, modular constraints, or bounded optimization), this linear solver is still the best first checkpoint for feasibility and structure.