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.

For example, the equation has many solutions over the reals. Here's a solution:

However, this equation has no nonzero integer solutions. This is a
special case of * Fermat's Last Theorem*.

On the other hand, the following equation has infinitely many integer solutions:

and are examples of solutions.

In this section, I'll look at equations like the last one. They're
called * linear Diophantine equations*.

* Theorem.* Let . Consider the Diophantine
equation

(a) If , there are no solutions.

(b) If , there are infinitely many solutions of the form

Here is a particular solution, and .

If you've had a course in differential equations, you may have seen something like this. and give a general solution to the homogeneous equation

is a particular solution to . Their sum gives a general solution to the given (nonhomogeneous) equation.

Before I give the proof, I'll give some examples, and also discuss the three variable equation .

* Example.* Solve .

Since , there are infinitely many solutions. Divide the equation by 3 to get

By inspection, and is a particular solution. Hence, the general solution is

For example, setting produces the solution , .

In general, you may not be able to see a particular solution by inspection. In that case, you can use the Extended Euclidean algorithm to generate one. We'll see how to do this in examples that follow.

* Example.* Solve .

Since , the equation has no solutions.

* Example.* Find all the solutions to the following Diophantine equation for
which x and y are both positive.

, so there are solutions.

It is too hard to guess a particular solution, so I'll use the Extended Euclidean algorithm:

Matching this with the given equation , I see that is a particular solution. The general solution is

I want solutions for which x and y are both positive. So

The integers which satisfy both of these inequalities are . Here are the values of x and y:

The solutions are , , and .

The requirement that the solutions be positive can come up in real-world problems.

* Example.* Phoebe buys large shirts for $18 each
and small shirts for $11 each. The shirts cost a total of $1188. What
is the smallest total number of shirts she could have bought?

Let x be the number of large shirts and let y be the number of small shirts. Then

Since , there are solutions.

I'll use the Extended Euclidean algorithm to get a particular solution:

and is a particular solution. The general solution is

Since the number of shirts can't be negative, I have and .

Thus, .

The total number of shirts is

For , this is smallest for , which gives

She bought 66 large shirts, no small shirts, and a total of 66 shirts.

Consider a 3-variable equation

The equation has solutions if and only if . If it has solutions, there will be infinitely many, determined by two integer parameters.

You can solve a 3-variable equation by reducing it to a 2-variable equation. Group the first two terms and factor out the greatest common divisor of their coefficients. Introduce a new variable, defining it to be what is left after the greatest common divisor is factored out. The new equation is a 2-variable Diophantine equation, which you can solve using the method described earlier.

* Example.* Find the general solution to the
following Diophantine equation.

Let .

and is a particular solution. So

Then

and is a particular solution. The general solution is

A general linear Diophantine equation has the form

There are solutions if . If there is a solution, it will in general have parameters --- exactly as you'd expect from linear algebra.

Here's the proof of the theorem for the two-variable case.

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

* Case 1.* Suppose . If x and y are solutions to the
equation, then

This contradiction shows that there cannot be a solution.

* Case 2.* Suppose . Write for . There are integers m and n such
that

Then

Hence, , , is a solution.

Suppose , , is a particular solution. Then

This proves that , is a solution for every .

Finally, I want to show that every solution has this form. Suppose then that is a solution. Then and imply

Therefore,

Now divides the left side, so it divides the right side. However, . Therefore,

Thus,

Substitute back into the last x-y equation above:

Thus,

Copyright 2019 by Bruce Ikenaga