# Linear Diophantine Equations

• A Diophantine equation is an equation which is to be solved over the integers.
• A linear Diophantine equation of the form has solutions if and only if . There is a similar result for linear Diophantine equations in more than 2 variables.

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. has many solutions over the reals; for example,

However, this equation has no nonzero integer solutions.

Example. Since , there are integers x and y such that .

For example, , and . That is, the Diophantine equation has solutions --- in fact, infinitely many solutions.

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 .

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. By trial and error, , , is a particular solution. Hence, the general solution is

For example, setting produces the solution , .

Example. Solve .

Since , the equation has no solutions.

Example. Solve

First, I'll factor out of the first two coefficients:

Notice that , so those two fractions are actually integers. I'm not simplifying so that you can see what's going on.

Let

The equation becomes

, so this two variable equation is solvable. , , is a particular solution, so the general solution is

Now I have to find x and y:

Thus,

This is a two variable equation. Since , it's solvable. , , is a particular solution. Therefore, the general solution is

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

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

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

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

Case 1. Suppose . If x and y solve 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 this back into the last x-y equation:

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