Linear Diophantine Equations


A Diophantine problem is one in which the solutions are required to be integers. Abusing terminology, I'll refer to Diophantine equations, meaning equations which are to be solved over the integers.


Example. $x^3 + y^3 = z^3$ has many solutions over the reals; for example,

$$x = 1, \quad, y = 1, \quad z = {\root 3 \of 2}.$$

However, this equation has no nonzero integer solutions.


Example. Since $(9,100) = 1$ , there are integers x and y such that $9x + 100y = 1$ .

For example, $9\cdot (-11) +
   100\cdot 1 = 1$ , and $9\cdot 89 + 100\cdot (-8) = 1$ . That is, the Diophantine equation $9x + 100y = 1$ has solutions --- in fact, infinitely many solutions.


Theorem. Let $a, b, c \in \integer$ . Consider the Diophantine equation

$$ax + by = c.$$

(a) If $(a,b) \notdiv c$ , there are no solutions.

(b) If $(a,b) = d \mid c$ , there are infinitely many solutions of the form

$$x = \dfrac{b}{d}k + x_0, \quad y = -\dfrac{a}{d}k + y_0.$$

Here $(x_0,y_0)$ is a particular solution, and $k \in \integer$ .

Before I give the proof, I'll give some examples, and also discuss the three variable equation $ax + by + cz = d$ .


Example. Solve $6x + 9y = 21$ .

Since $(6,9) = 3 \mid 21$ , there are infinitely many solutions. By trial and error, $x = -7$ , $y = 7$ , is a particular solution. Hence, the general solution is

$$x = 3k - 7, \quad y = -2k + 7.$$

For example, setting $k =
   5$ produces the solution $x = 8$ , $y = -3$ .


Example. Solve $6x + 9y = 5$ .

Since $(6,9) = 3 \notdiv 5$ , the equation has no solutions.


Example. Solve

$$3x + 3y + 5z = 10.$$

First, I'll factor $(3,3)$ out of the first two coefficients:

$$(3,3)\left(\dfrac{3}{(3,3)}x + \dfrac{3}{(3,3)}y\right) + 5z = 10.$$

Notice that $(3,3) = 3$ , so those two fractions are actually integers. I'm not simplifying $\dfrac{3}{(3,3)}$ so that you can see what's going on.

Let

$$w = \dfrac{3}{(3,3)}x + \dfrac{3}{(3,3)}y.$$

The equation becomes

$$(3,3)w + 5z = 10, \quad\hbox{or}\quad 3w + 5z = 10.$$

$(3,5) = 1 \mid 10$ , so this two variable equation is solvable. $w = 5$ , $y = -1$ , is a particular solution, so the general solution is

$$w = 5s + 5, \quad z = -3s - 1.$$

Now I have to find x and y:

$$w = \dfrac{3}{(3,3)}x + \dfrac{3}{(3,3)}y, \quad\hbox{so}\quad w = x + y.$$

Thus,

$$x + y = 5s + 5.$$

This is a two variable equation. Since $(1,1) = 1 \mid 5s + 5$ , it's solvable. $x = 5$ , $y = 5s$ , is a particular solution. Therefore, the general solution is

$$x = t + 5, \quad y = 5s - t.$$

All together, the general solution to the original three variable equation is

$$x = t + 5, \quad y = 5s - t, \quad z = -3s - 1.\quad\halmos$$


In general, if there is a solution to the linear Diophantine equation

$$a_1x_1 + \cdots a_nx_n = c,$$

the solution will depend on $n - 1$ parameters --- exactly as you'd expect from linear algebra.

Proof. (two variable case) Consider the linear Diophantine equation

$$ax + by = c.$$

Case 1. Suppose $(a,b) \notdiv c$ . If x and y solve the equation, then

$$(a,b) \mid ax + by = c.$$

This contradiction shows that there cannot be a solution.

Case 2. Suppose $(a,b) \mid c$ . Write $c = k(a,b)$ for $k \in \integer$ . There are integers m and n such that

$$am + bn = (a,b).$$

Then

$$amk + bnk = (a,b)k = c.$$

Hence, $x = km$ , $y = kn$ , is a solution.

Suppose $x = x_0$ , $y = y_0$ , is a particular solution. Then

$$a\left(\dfrac{b}{d}k + x_0\right) + b\left(-\dfrac{a}{d}k + y_0\right) = \dfrac{ab}{d}k - \dfrac{ab}{d}k + (ax_0 + by_0) = 0 + c = c.$$

This proves that $x =
   \dfrac{b}{d}k + x_0$ , $y = -\dfrac{a}{d}k + y_0$ is a solution for every $k \in \integer$ .

Finally, I want to show that every solution has this form. Suppose then that $(x,y)$ is a solution. Then $ax + by = c$ and $ax_0 +
   by_0 = c$ imply

$$a(x - x_0) + b(y - y_0) = c - c = 0.$$

Therefore,

$$\dfrac{a}{(a,b)}(x - x_0) + \dfrac{b}{(a,b)}(y - y_0) = 0,$$

$$\dfrac{a}{(a,b)}(x - x_0) = -\dfrac{b}{(a,b)}(y - y_0).$$

Now $\dfrac{a}{(a,b)}$ divides the left side, so it divides the right side. However, $\left(\dfrac{a}{(a,b)},\dfrac{b}{(a,b)}\right) = 1$ . Therefore,

$$\dfrac{a}{(a,b)} \bigm| y - y_0, \quad\hbox{or}\quad y - y_0 = k\cdot \dfrac{a}{(a,b)} \hbox{ for some } k.$$

Thus,

$$y = y_0 + k\cdot \dfrac{a}{(a,b)}.$$

Substitute this back into the last x-y equation:

$$\dfrac{a}{(a,b)}(x - x_0) = -\dfrac{b}{(a,b)}(y - y_0) = -\dfrac{b}{(a,b)}k\cdot \dfrac{a}{(a,b)},$$

$$x - x_0 = -k\cdot \dfrac{b}{(a,b)},$$

$$x = x_0 - k\cdot \dfrac{b}{(a,b)}.$$

This is the result stated in the theorem (with an unimportant switch of k and $-k$ .)


Send comments about this page to: Bruce.Ikenaga@millersville.edu.

Bruce Ikenaga's Home Page

Copyright 2008 by Bruce Ikenaga