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.
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.
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:
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
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
Now divides the left side, so it divides the right side. However, . Therefore,
Substitute this back into the last x-y equation:
This is the result stated in the theorem (with an unimportant switch of k and .)
Bruce Ikenaga's Home Page
Copyright 2008 by Bruce Ikenaga