How to solve diophantine equations?
I want to show you a method how to solve linear diophantine equations. The method works for equations in any number of variables. What if the “any number” is ? Well, if a linear equation of the form
is given with the integers
, then if
is zero, then
is zero, too, and every
in the domain is a solution. On the other hand, if
is different from zero, then the only solution is
, which may or may not be an integer. Hence, from our point of view the linear equations in one unknown are completely uninteresting.
The next simplest case is of the equations in two unknowns: . Here we shall suppose that
are integers and we are looking for integer solutions
and
. So, when talking about a “solution” of our equation we always mean “integer solution”. We also suppose that
and
are different from zero: otherwise we have an equation with less than two unknowns — we’re done with that case.
Considering integer numbers divisibility is the most powerful tool. In our case it is clear that any number which divides both and
also divides
— no matter what
and
are. In other words, if the numbers
and
have a common divisor which does not divide
, then the equation has no solution. On the other hand, as every common divisor of
and
is a divisor of their greatest common divisor, abbreviated as gcd, we have a necessary condition for the solvability of our equation: the gcd of
and
divides
. For instance, the diophantine equation
has no solution. This is clear, as the left side is always an even number, no matter what
and
are.
This is great! Given an equation of the above form it is extremely easy to check if this condition is satisfied — if not, then we are done, there is no solution. But what if the condition is satisfied? “Necessary” does not mean “sufficient”: maybe our condition does not guarantee the existence of a solution, maybe the “necessary” is not “sufficient”. So, from now on we suppose that the gcd of and
divides
— then we can divide both sides of our equation by this gcd to obtain a similar equation, just the corresponding new
and
have gcd
. And this new equation is equivalent to the original one, which means that they have the same solutions. Consequently, we can simplify our problem by assuming that in the original equation
and
are relatively prime numbers: their gcd is
. Then the original necessary condition is automatically satisfied:
divides
, no matter what
is.
Now our job is to find whole numbers such that
. It is obvious that the expression
takes both positive and negative values; let
denote its smallest positive value. A fundamental property of the natural number system is the Well Ordering Principle: every non-empty set of natural numbers has a smallest element. So, when considering all positive numbers of the form
with some integer numbers
then there is a smallest one of them which will be denoted by d. In other words, we have
with some integers
and
, and
is the smallest positive number with this property. We will show that
divides both
and
.
Here we use another basic tool which works in the world of integers: the Division Algorithm. It says that we can find integers and
such that
, where
. This is the well-known algorithm which produces the quotient
and the remainder
. In this case we have
We use this silly form to emphasize that is also a possible value of the expression
— we just replace
by
and
by
. As
is non-negative and smaller than
, hence, by the choice of
it must be zero:
. This means that
is divisible by
. By similar reasoning we have that
divides
, too. Thus
is a common divisor of
and
. On the other hand, if
is any common divisor of
and
then we have
and
with some integers
, consequently
Thus shows that divides
, hence the positive number
has the following crucial properties: it is a common divisor of
and
, and it is divisible by any common divisor of
and
. In other words,
is exactly the greatest common divisor of
and
— in our case it is
.
Oops! We have proved that if and
are relatively prime numbers than the equation
has a solution
in the integers. Going back to the original problem, we have proved that if the gcd of
and
divides
, then
has a solution
in the integers. Summarizing, we completely proved the following necessary and sufficient condition about the solvability of diophantine equations:
Theorem
Given the whole numbers the equation
is solvable in the set of whole numbers if and only if the greatest common divisor of
and
divides
.
For instance, the equation has integer solutions, but the equation
does not have. It’s good to know before we start to find a solution. Also, as a consequence we have that
is always solvable if
is the greatest common divisor of
and
. Another corollary is that if
and
are relatively prime numbers, then every integer can be written in the form
with some whole numbers
.
There is only one open question left: how to find the solutions if they exist? We present a solution method on the following example: . Here the gcd of
and
is
, hence the equation is solvable. We write the equation in the following form:
in other words, we express that term of and
where the absolute value
or
is smaller. If they are equal, then we can choose any of them. Now we write our equation in the form
In other words, we separate those terms which are clearly divisible by , divide them by
, and then we have the remainder
. As
is a whole number, hence
is divisible by
, that is
with some integer
. We can write this in the form
. Now we repeat the above process: we express
:
Again, is an integer, hence
is divisible by
, that is
with some integer
. We infer
, and by the previous equation it follows
Going back to we have
Finally, we have the solution in the form
and here can be an arbitrary whole number. It is easy to check that
form a solution no matter what is
:
And our process shows that indeed, every solution must have this form with some . In the above solution
is an integer parameter, and as
runs through the set of all integers the points
run through all points with integer coordinates on the straight line
.
From this all we have to remember the following crucial facts:
- The Well Ordering Principle, which says that any non-empty set of natural numbers has a smallest element. Think about this! If you want to prove this statement somehow, then you will see that the reason is that in the world of natural numbers there is no infinite strictly decreasing sequence. No matter where you start, if you pick smaller and smaller natural numbers, then your process will terminate after a finite number of steps. The integers do not have this property: we can take the negative integers
etc., and this process never terminates, there is always a smaller one. You may think that this is because there is a smallest natural number:
, but there is no smallest integer number. No, no, this is not the reason, as it is shown by the example of rational numbers. Non-negative rational numbers have a smallest number, the zero, but still we can construct infinite decreasing sequence of non-negative rational numbers: for instance, the reciprocals of positive integers have this property. The Well Ordering Principle is a very own property of the natural number system.
- The Division Algorithm, which says that given two whole numbers
with
is non-zero then
can be divided by
with remainder in a unique way: we can always find two unique whole numbers
and
such that
, and
. Here we call
the quotient and
the remainder.