Linear Diophantine Equations: Integer Solutions Explained

A linear Diophantine equation is an equation like ax + by = c where we seek solutions in integers only. The name honours Diophantus of Alexandria, and the integer restriction is what makes the problem interesting: 6x + 10y = 14 has the real solution x = 1, y = 0.8, but does it have an integer one?

These equations matter because many real problems demand whole-number answers — you cannot buy half a ticket or schedule a third of a bus. They also lead directly to modular inverses, the engine inside RSA encryption.

Key Concepts

• Diophantine: an equation where only integer solutions count.
• Solvability condition: ax + by = c has integer solutions exactly when gcd(a, b) divides c.
• Particular solution: any single integer pair (x0, y0) that works, found via the extended Euclidean algorithm.
• General solution: all solutions are generated from one particular solution by shifting along the line.
• Homogeneous case: ax + by = 0 has solutions built from steps of size b/d and a/d, where d = gcd(a, b).

Formulas

• Solvable exactly when d divides c, where d = gcd(a, b).
• General solution: x = x0 + (b/d) times t, y = y0 − (a/d) times t, for any integer t.
• Here (x0, y0) is one particular solution and the t-terms step to every other integer solution.
• Finding (x0, y0): use the extended Euclidean algorithm on a and b, then scale to reach c.

Worked Example

Solve 6x + 10y = 14 in integers. First d = gcd(6, 10) = 2, and 2 divides 14, so solutions exist. Spot a particular solution: 6 times (−1) + 10 times 2 = −6 + 20 = 14, so x0 = −1, y0 = 2. With b/d = 5 and a/d = 3, the general solution is x = −1 + 5t, y = 2 − 3t. Check t = 1: x = 4, y = −1, and 6 times 4 + 10 times (−1) = 24 − 10 = 14. Check t = −1: x = −6, y = 5, and −36 + 50 = 14. Contrast 6x + 10y = 15: gcd 2 does not divide 15, so no integer solution exists.

Common Misconceptions

• "Every linear equation has integer solutions." Only when gcd(a, b) divides c — the equation 6x + 10y = 15 proves otherwise.
• "There is at most one solution." When solvable, there are infinitely many, spaced by the (b/d, −a/d) steps.
• "You can just divide through by c." Dividing changes the integer structure; the correct reduction divides a, b, c by d = gcd(a, b) only when d divides c.

Real-World Applications

• Coin problems: which amounts can be formed with given denominations.
• Scheduling: aligning repeating cycles, like two buses with different periods meeting at a stop.
• Cryptography: computing modular inverses for RSA key generation via the extended Euclidean algorithm.

A linear Diophantine equation ax + by = c is solvable in integers exactly when gcd(a, b) divides c, and then every solution is x = x0 + (b/d)t, y = y0 − (a/d)t. One divisibility check decides existence; one particular solution unlocks them all.