Suppose a vending machine only takes 3-dollar coins and 5-dollar coins, and you owe exactly 47 dollars. How many of each coin do you need? This is not an algebra question with one clean answer like x = 6.2 — a fraction of a coin is meaningless. You need whole numbers, and only whole numbers, of each coin.

Equations we insist on solving in whole numbers only are called Diophantine equations, named for Diophantus of Alexandria, who studied them some 1,800 years ago. The simplest kind is linear:

where a, b, c are given integers and we want integer x, y. Over the real numbers this is just a line with infinitely many points on it. The twist — and the number theory — is the demand that x and y land exactly on lattice points: the grid of whole-number coordinates.

When is it solvable?

Every combination ax + by is a multiple of \gcd(a, b) — that was the lesson of Bézout's identity. So the equation can only hold if c is itself such a multiple. That condition is also sufficient: if d = \gcd(a,b) divides c, Bézout's identity itself hands you a solution, scaled up to size.

So 6x + 9y = 20 is hopeless (the left side is always a multiple of 3, and 3 \nmid 20), while 6x + 9y = 21 is fine, since 3 \mid 21. Always run this one-line check before hunting for a solution — no amount of clever searching will find one if the divisibility test fails.

Worked example: solving one completely

Solve 12x + 8y = 20 in integers. First the check: \gcd(12, 8) = 4, and 4 \mid 20 — solvable.

Run the extended Euclidean algorithm on 12 and 8:

Back-substituting the single step: 4 = 12 - 1 \cdot 8, so x_0 = 1, y_0 = -1 satisfies 12x_0 + 8y_0 = 4. Scale by c/d = 20/4 = 5:

One particular solution is (x, y) = (5, -5). To get every solution, slide along the line in steps of b/d = 2 and a/d = 3:

Try t = -2: (x, y) = (1, 1), and indeed 12 \cdot 1 + 8 \cdot 1 = 20 — a much friendlier-looking solution, hiding inside the same family.

Worked example: the stamp problem

Back to the coins (or stamps — the maths is identical): how many 3-unit and 5-unit pieces make exactly 47? We want non-negative integers x, y with

Check first: \gcd(3, 5) = 1, which divides everything — always solvable. Spot one solution by inspection: y = 1 \Rightarrow 3x = 42 \Rightarrow x = 14. So (x_0, y_0) = (14, 1) works. With d = 1, the general solution steps by b/d = 5 and a/d = 3:

Now add the real-world constraint that both counts must be \geq 0: 14 - 5t \geq 0 gives t \leq 2.8, and 1 + 3t \geq 0 gives t \geq -1/3. So t \in \{0, 1, 2\} — exactly three ways to make 47:

Check the middle one: 3 \cdot 9 + 5 \cdot 4 = 27 + 20 = 47. The equation itself has infinitely many integer solutions, but only a short, finite window of them makes sense once you demand non-negative counts of coins.

Finding all solutions, in general

From one solution (x_0, y_0), every other is reached by sliding along the line in integer steps. Writing d = \gcd(a,b):

The shifts b/d and -a/d are the smallest whole steps that keep ax + by unchanged: increasing x by b/d adds a \cdot b/d, while decreasing y by a/d subtracts b \cdot a/d — the two changes exactly cancel. Geometrically, the integer solutions are evenly spaced lattice points marching along the line, and questions like "find the non-negative solutions" become a matter of choosing the right range of t, exactly as in the stamp problem above. This same shape — a solvability condition plus a periodic family of answers — reappears for linear congruences.

Why the step sizes are $b/d$ and $a/d$

It's worth seeing why the general solution steps by exactly b/d and a/d, rather than just trusting the formula. Suppose (x, y) and (x_0, y_0) are both solutions of ax + by = c. Subtracting the two equations:

Write a = d a' and b = d b', where a' = a/d and b' = b/d are coprime (dividing out the gcd always leaves coprime leftovers). Cancelling d from both sides gives

Now b' divides the left side, and since \gcd(a', b') = 1, b' must divide x - x_0 outright. So x - x_0 = b' t = (b/d)\,t for some integer t, and substituting back gives y - y_0 = -a' t = -(a/d)\,t. That's exactly the shift used above — it isn't a guess, it falls straight out of coprimality once the common factor d is stripped away.