Linear Diophantine Equations, Explained
After reading this you will know when ax + by = c has integer solutions, how to find one solution, and how to write every solution from that single one.
What a linear Diophantine equation is
A linear Diophantine equation asks for integer values of the unknowns. The plain equation 12x + 18y = 30 has infinitely many real solutions, but here you only accept whole numbers for x and y. That single restriction changes everything: some equations that look reasonable have no integer solution at all, and the ones that do have solutions spaced out in a regular pattern.
The classic hook is a coin or postage problem. Suppose you have 12-cent stamps and 18-cent stamps, and you want to make exactly 30 cents of postage using whole stamps, where negative counts mean returning stamps. The equation is 12x + 18y = 30. One answer is x = -1, y = 3, since 12(-1) + 18(3) = -12 + 54 = 42. That is wrong, so check again: you want 30, and 12(4) + 18(-1) = 48 - 18 = 30. That works. Finding these by hand is tedious, which is exactly what the formula below removes.
When to use it, and when not
Use this method whenever a problem reduces to "combine two whole quantities with fixed weights to hit a target." Making change, tiling lengths, balancing two gear ratios, and counting steps of two sizes all fit the form ax + by = c.
Do not use it when fractions are allowed, when you have three or more unknowns (that needs a different, though related, approach), or when the coefficients are not integers. If your problem is really about remainders, for example "find x with x \equiv 3 \pmod{7}," reach for the Congruence solver instead, since congruences and Diophantine equations are two views of the same arithmetic.
The existence test and the formula
Everything starts with the greatest common divisor of a and b, written g = \gcd(a, b).
Here g = \gcd(a, b) and g \mid c means g divides c exactly, with no remainder. The reason is direct: every combination ax + by is a multiple of g, because g divides both a and b. So if c is not a multiple of g, no integer choice can reach it. If c is a multiple of g, the extended Euclidean algorithm produces integers that hit it.
Once you have any one solution (x_0, y_0), the full family is:
Here t runs over all integers, b/g and a/g are the reduced coefficients, and each integer t gives a different valid pair. The step in x is b/g and the step in y is -a/g, so consecutive solutions are evenly spaced. That spacing is the single most useful fact for counting how many solutions land in a given range.
Why does the change (x_0 + b/g,\ y_0 - a/g) stay a solution? Plug it in: the extra term is a(b/g) - b(a/g) = ab/g - ab/g = 0. It cancels exactly, so the equation still holds.
Worked example with the demo data
Solving 12x + 18y = 30
Use the demo values a = 12, b = 18, c = 30. Press Calculate to reproduce every number below.
- Compute g = \gcd(12, 18) = 6.
- Check divisibility: 30 / 6 = 5, a whole number, so 6 \mid 30. Solutions exist.
- Solve the reduced equation. Divide through by
6: 2x + 3y = 5. A Bézout pair for \gcd(2,3)=1 is 2(-1) + 3(1) = 1. Scale by5: 2(-5) + 3(5) = 5, giving x_0 = -5, y_0 = 5. - Verify: 12(-5) + 18(5) = -60 + 90 = 30. Correct.
- Write the family. Here b/g = 18/6 = 3 and a/g = 12/6 = 2, so x = -5 + 3t and y = 5 - 2t.
The particular solution the calculator prints may look different from (-5, 5), and that is fine. Any two particular solutions differ by a whole number of steps. For instance t = 3 gives x = 4, y = -1, matching the postage answer from the first section.
| t | x = -5 + 3t | y = 5 - 2t | 12x + 18y |
|---|---|---|---|
| -1 | -8 | 7 | 30 |
| 0 | -5 | 5 | 30 |
| 1 | -2 | 3 | 30 |
| 2 | 1 | 1 | 30 |
| 3 | 4 | -1 | 30 |
Seeing the solution lattice
Plotting the integer solutions makes the even spacing obvious. Every valid point sits on the real line 12x + 18y = 30, and the integer ones appear at a fixed horizontal step of b/g = 3 and vertical step of a/g = 2.
Reading and interpreting the result
The calculator reports three things. First, a yes or no on existence, driven entirely by whether g divides c. Second, one particular solution (x_0, y_0). Third, the general family in terms of a free parameter t.
- Particular solution
- Any single pair that satisfies the equation, such as (x_0, y_0) = (-5, 5) for the demo. It is a starting anchor, not the only answer.
- General solution
- The formula x = x_0 + (b/g)t, y = y_0 - (a/g)t that generates every integer solution as
tranges over the integers. - Step size
- The gap between neighboring solutions: b/g in
xand a/g iny. For the demo that is 3 and 2.
If your real problem requires x \ge 0 and y \ge 0, use the family to find the allowed range of t. For the demo, x = -5 + 3t \ge 0 forces t \ge 2, and y = 5 - 2t \ge 0 forces t \le 2. Only t = 2 survives, giving the single non-negative solution (1, 1).
Common mistakes
The most frequent error is treating one particular solution as the answer. Because solutions repeat every b/g steps in x, a problem asking "how many ways" almost always has more than one, and often infinitely many without a range constraint.
Two more traps show up often. First, forgetting the sign in the y term: the formula subtracts (a/g)t, so if you add it you will drift off the line. Test with t = 1: correct gives y = 5 - 2 = 3 and 12(-2) + 18(3) = 30, while the wrong sign gives y = 7 and 12(-2) + 18(7) = 102 \ne 30.
Second, dividing the coefficients but not c when reducing, or the reverse. All three must be divided by g together. From 12x + 18y = 30 the correct reduction is 2x + 3y = 5, not 2x + 3y = 30.
Related tools
Diophantine equations connect closely to modular arithmetic. Solving ax \equiv c \pmod{b} is the same as solving ax + by = c for some y, so the Congruence solver is the natural companion for remainder problems. The greatest common divisor and the reductions rely on factoring, which the Prime number tools support. If you are computing in a fixed radix rather than base ten, the Base-N arithmetic page handles that directly. For unrelated discrete work, the Set calculator and the Truth table generator cover set operations and logic.
Frequently asked questions
Why does gcd decide whether a solution exists?
Every value of ax + by is a multiple of \gcd(a, b), since g divides both terms. So the target c is reachable only if it too is a multiple of g. For 12x + 18y, every result is a multiple of 6, which is why c = 30 works but c = 31 does not.
How many integer solutions are there?
Without a range restriction there are infinitely many, one for each integer t. With bounds such as x \ge 0 and y \ge 0, count the integers t that satisfy both inequalities. In the demo only t = 2 qualifies, so there is exactly one non-negative solution.
Can the coefficients or c be negative?
Yes. The existence test still uses \gcd(|a|, |b|), which is always positive, and the family formula is unchanged. A negative c just shifts the particular solution.
What if gcd(a, b) does not divide c?
Then no integer solution exists, and the calculator reports that. For example 12x + 18y = 31 has none, because 31/6 is not a whole number.
Does the answer depend on which particular solution I start from?
No. Any valid (x_0, y_0) generates the same complete set, just with the parameter t shifted. Two particular solutions always differ by a whole number of steps of size b/g in x.
Related tools
Truth Table Generator
Full truth tables plus DNF/CNF simplification.
Prime Number Tools
Primality tests, the nth prime, prime ranges and π(x).
Set Calculator
Union, intersection, differences and power sets.
Base-N Arithmetic
Add, subtract, multiply and divide directly in any base.
Congruence Solver (CRT)
Linear congruences and Chinese Remainder Theorem systems.
3D Solid Geometry Calculator
Volume and surface area of spheres, cones, prisms and more.