Solving ax + by = c in the integers

A Diophantine equation is one whose solutions are required to be integers. The simplest, ax + by = c, is solved completely thanks to Bézout.

When do solutions exist?

The equation a x + b y = c has integer solutions if and only if GCD(a , b) divides c.

The condition is necessary: GCD(a,b) divides ax and by, hence their sum c. It is sufficient thanks to Bézout — just multiply the identity by the right factor.

6x + 9y = 21     GCD(6,9) = 3,  and 3 | 21     ->  solutions exist
6x + 9y = 20     3 does not divide 20          ->  NO solution

The second line can also be read directly: 6x + 9y is always a multiple of 3, so it can never be 20.

The full method

1. compute d = GCD(a , b) and check that d divides c
2. simplify the equation by d
3. find ONE particular solution (Bézout, or by inspection)
4. write ALL the solutions

On an example:

12 x + 18 y = 30

1. GCD(12,18) = 6,  and 6 | 30      ->  solutions exist
2. divide by 6:   2 x + 3 y = 5
3. obvious solution:  x = 1, y = 1   (2 + 3 = 5)     ✔

All the solutions

Once the equation is reduced to a'x + b'y = c' with a' and b' coprime, and (x0 ; y0) a particular solution:

x = x0 + b' k
y = y0 - a' k              for every integer k

On the example  2x + 3y = 5,  with (x0 ; y0) = (1 ; 1):

   x = 1 + 3k
   y = 1 - 2k

   k = 0  ->  (1 ; 1)      2 + 3 = 5    ✔
   k = 1  ->  (4 ; -1)     8 - 3 = 5    ✔
   k = -1 ->  (-2 ; 3)    -4 + 9 = 5    ✔

So there are infinitely many solutions, evenly spaced.

Why this form? If (x ; y) and (x0 ; y0) are two solutions, their difference satisfies a'(x - x0) = -b'(y - y0). Since a' and b' are coprime, Gauss's theorem forces b' to divide x - x0 — hence x = x0 + b'k. The whole chapter comes together here.

A concrete problem

A machine gives change only in €2 and €5 coins. How can exactly €31 be returned?

2x + 5y = 31       GCD(2,5) = 1 divides 31   ->  possible

particular solution: y = 1, x = 13   (26 + 5 = 31)

general solutions:   x = 13 + 5k
                     y = 1 - 2k

But a number of coins must be non-negative:

x ≥ 0  ->  13 + 5k ≥ 0  ->  k ≥ -2.6  ->  k ≥ -2
y ≥ 0  ->   1 - 2k ≥ 0  ->  k ≤ 0.5   ->  k ≤ 0

k ∈ {-2 ; -1 ; 0}   ->   (3 ; 5)   (8 ; 3)   (13 ; 1)

Three concrete solutions: 3 coins of €2 and 5 of €5, or 8 and 3, or 13 and 1. This last step — restricting to admissible solutions — is what separates an exercise from a real problem.

Where such equations appear

Cryptography      : modular inverse, RSA keys
Calendars         : synchronising cycles of different lengths
Error-correcting codes : the Chinese remainder theorem
Cutting, change   : change-making, cutting-stock optimisation
Music             : scales and temperaments (frequency ratios)

Summary

• ax + by = c has integer solutions iff GCD(a , b) divides c.
• Method: check, simplify by the GCD, find one solution, generalise.
• General solutions: x = x0 + b'k, y = y0 - a'k with a', b' coprime.
• This form is proved by Gauss's theorem.
• A concrete problem often adds non-negativity constraints that reduce it to finitely many solutions.