Linear Diophantine Equation Solver with Integer Solutions
Solve ax + by = c over the integers. Check existence, find one exact pair, and describe every solution. Your coefficients stay in your browser.
Enter the equation
a·x + b·y = c
Use signed whole numbers of up to 300 digits. Commas, spaces, or underscores may group digits in sets of three.
Integer solutions
Your result will appear here.
For the starting equation 15x + 21y = 84, select Solve equation to get a particular solution and the complete family.
When does ax + by = c have integer solutions?
Let d = gcd(a, b), using a non-negative greatest common divisor. When a and b are not both zero, the equation has an integer solution exactly when d divides c.
ax + by = c is solvable ⇔ gcd(a,b) | c
If d does not divide c, no pair of integers (x, y) can satisfy the equation.
The reason is Bézout’s identity. The extended Euclidean algorithm finds integers s and t with as + bt = d. If c = dq, multiplying by q gives the particular solution x0 = sq, y0 = tq.
The complete family of solutions
Suppose (x0, y0) is one solution and d = gcd(a, b). Every integer solution is:
x = x0 + (b/d)k
y = y0 − (a/d)k
k ∈ ℤ
Changing k adds b/d to x and subtracts a/d from y. The equation stays balanced because the change in its left side is:
a(b/d)k + b(−a/d)k = 0
The calculator chooses a compact starting pair by shifting the extended-Euclidean result so x0 is as close to zero as possible when b ≠ 0.
Worked example: 15x + 21y = 84
Check the divisibility condition
gcd(15, 21) = 3, and 3 divides 84 because 84 ÷ 3 = 28. Integer solutions therefore exist.
Bézout’s identity gives 15(3) + 21(−2) = 3. Multiplying by 28 first gives (84, −56), then shifting within the family gives the smaller particular solution (0, 4).
Write and verify all solutions
x = 0 + 7k y = 4 − 5k
For k = 2, (x, y) = (14, −6):
15(14) + 21(−6) = 210 − 126 = 84
Zero coefficients and special cases
Equation form
Integer-solution rule
a and b both nonzero
Solutions exist exactly when gcd(a, b) divides c; the general two-variable formula applies.
a = 0, b ≠ 0
y = c/b when b divides c, while x may be any integer.
a ≠ 0, b = 0
x = c/a when a divides c, while y may be any integer.
a = b = 0, c = 0
Every integer pair (x, y) is a solution.
a = b = 0, c ≠ 0
No solution, because the left side is always zero.
Linear Diophantine equation FAQ
When does ax + by = c have integer solutions?
When a and b are not both zero, solutions exist exactly when gcd(a, b) divides c. The solver checks this before constructing a solution.
How many solutions are there?
A solvable equation with at least one nonzero coefficient has infinitely many integer solutions. The parameter k runs through all integers to generate them.
What does the parameter k do?
It chooses one member of the solution family. Replacing k with any other integer gives another exact solution without changing the equation.
Can coefficients be negative or zero?
Yes. All four inputs accept signed integers. The result uses the original signs and separately explains the all-zero coefficient case.
Why might another solver show a different particular solution?
Particular solutions are not unique. Two correct starting pairs differ by a shift of (b/d, −a/d) times an integer. This solver selects a compact representative.
How large can the inputs be?
Each input may contain up to 300 digits after grouping separators are removed. JavaScript BigInt arithmetic keeps every displayed integer exact; long Euclidean tables are abbreviated on screen.
Are my inputs private?
Yes. Validation and arithmetic happen entirely in your browser. The tool does not upload, store, or add your coefficients to the URL.
