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:
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.