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.

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,

Contact information