The idea: integer points on a line
A linear Diophantine equation is ax + by = c where a, b, c are whole numbers and only whole-number answers x, y count. Over the real numbers, ax + by = c is a straight line. Mark every point with whole coordinates (the integer lattice) and the question becomes: which lattice points does the line go through? The answer is always one of two: none at all, or infinitely many, spaced evenly along the line.
When is there a solution?
Let g = gcd(a, b). For whole x and y, ax and by are multiples of g, so ax + by is a multiple of g too. If g does not divide c, nothing works. For 4x + 6y = 9 the left side is always even and 9 is odd (Demo: 4x + 6y = 9 has no solution). On the plot, the dashed lines 4x + 6y = 8 and 4x + 6y = 10 pass through lattice points, and the line for 9 runs exactly halfway between them.
The other direction is Bézout's identity: there are always whole s, t with s·a + t·b = g. So when g divides c, a solution exists. Together:
| condition | integer solutions |
|---|---|
| g divides c | infinitely many, (x₀, y₀) + k·(b/g, −a/g) |
| g does not divide c | none |
One solution from extended Euclid
The extended Euclidean algorithm keeps rows r, s, t with r = s·a + t·b. It starts with the two numbers themselves and makes each new row as the row two up minus q times the row above, where q is the quotient of their r values. When r reaches 0, the row above holds g and the Bézout coefficients. For a = 3, b = 5:
r q s t
5 — 0 1
3 — 1 0
2 1 −1 1
1 1 2 −1 ← g = 1: 2·3 + (−1)·5 = 1
0 2 −5 3Multiply by c/g = 7: 3·14 + 5·(−7) = 7, so (x₀, y₀) = (14, −7) is a solution (Demo: 3x + 5y = 7). It is far off the plot, which is normal: Bézout coefficients times c can be large. The same table appears, built step by step, on Euclidean Algorithm and Extended Euclid, Modular Inverse and Toy RSA.
All solutions: the step along the line
If (x, y) is a solution, so is (x + b/g, y − a/g), because a·(b/g) + b·(−a/g) = 0. Dividing by g gives the smallest step: a/g and b/g are coprime, and every solution is one of
x = x₀ + (b/g)·k, y = y₀ − (a/g)·k, k = …, −2, −1, 0, 1, 2, …For 4x + 6y = 10, g = 2 and the step is (3, −2). Stepping by (6, −4) would skip (1, 1) and every other point (Demo: 4x + 6y = 10). The page shifts (x₀, y₀) by whole steps to the solution nearest the middle of the plot, then walks both ways.
Solutions with x, y ≥ 0: coins and stamps
Many word problems want x, y ≥ 0: how many 5-cent and 7-cent stamps make 31 cents? The line 5x + 7y = 31 falls from left to right, so it crosses the first quadrant in a short piece, and only (2, 3) lands there (Demo: 5x + 7y = 31). The line 3x + 5y = 7 has no such point at all: 7 cannot be paid with 3s and 5s. In fact 7 = 3·5 − 3 − 5 is the largest amount that cannot, the Frobenius number of 3 and 5.
| equation | g | step | x, y ≥ 0 |
|---|---|---|---|
| 3x + 5y = 7 | 1 | (5, −3) | none |
| 4x + 6y = 10 | 2 | (3, −2) | (1, 1) |
| 5x + 7y = 31 | 1 | (7, −5) | (2, 3) |
| 2x − 3y = 1 | 1 | (3, 2) | infinitely many |
When a and b have opposite signs, as in 2x − 3y = 1, the line rises and the step (3, 2) points into the first quadrant, so there are infinitely many non-negative solutions (Demo: 2x − 3y = 1, a rising line).
The same equation hides inside the Chinese Remainder Theorem: x ≡ a₁ (mod m₁) and x ≡ a₂ (mod m₂) means x = a₁ + m₁u = a₂ + m₂v, which is m₁u − m₂v = a₂ − a₁. A modular inverse a⁻¹ mod n is the x in ax + ny = 1.
What the page leaves out
The page uses fixed small equations so every solution fits on one plot. It does not cover equations in three or more unknowns (solved one gcd at a time), counting the non-negative solutions in general, or non-linear Diophantine equations such as x² + y² = z² or Fermat's last theorem, where no single algorithm works (Hilbert's tenth problem).