In mathematics we usually consider functions and equations over the real numbers. This means that we can input numbers like , and in our functions and can expect outputs of that form as well. Solutions of such equations also typically allow for such forms. Diophantine equations are a bit different in that regard. A diophantine equation is a polynomial equation such that the only solutions that we are interested in are integers. In general a system of diophantine equations has more unknowns than it has equations. Over the reals this usually results in uncountable infinite many solutions, but with diophantine equations this is less often the case.
Most people that went to high school have heard of Pythagoras theorem, but let me repeat it for you. If we have a right angled triangle then if we square both side lengths of the sides connected to the right angle and add them together we get the side length of the side opposite the right angle. See the picture below for a visual representation of this.
But the question is now: what does this have to do with diophantine equations? Well, a mathematical representation of Pythagoras theorem is . This is a polynomial equation with 3 unknowns . And now we introduce the definition of a Pythagorean triple. A Pythagorean triple is a set of three integers such that they satisfy Pythagoras theorem. Hence a Pythagorean triple is an integer solution to a polynomial equation. The most common example of this is . But it turns out that there are infinitely many primitive Pythagorean triples. Now what do I mean by primitive? Primitive means that are coprime.
A good followup question is: why is the fact that there are infinitely many primitive Pythagorean triples a much stronger statement than the fact that there are infinitely many Pythagorean triples? This is due to the fact that we can generate infinitely many Pythagorean triples from the one that we already have. Because the fact that is a solution gives us all solutions of the form for any integer since .
One final thing that is interesting is Euclid’s formula for generating primitive Pythagorean triples. Euclid’s formula states that for positive integers such that , we have that is a Pythagorean triple and therefore a solution to our diophantine equation. To see this note that prove the fact that this is indeed a solutions. Note however that if both and are odd, we find that all numbers in the triple are even and hence divisible by 2. Since we want to find primitive Pythagorean triples, we can fix this by dividing the triple by 2. If we do so we do in fact obtain a primitive Pythagorean triple.
Linear diophantine equations
Linear diophantine equations are likely the easiest kind to solve. Note an example of a linear diophantine equation is where are integer and constant and are variables. Then using Bézout’s identity one can show that this equation has infinitely many solutions over the integers if . This means that must be a multiple of the greatest common divisor of and . Then the question is how we can find these solutions. First note that a homogenous solution to the equation is given by and since . Then note that the smallest integer solution must be given by and where to ensure that will still be integers. Hence the general solution of the homogeneous equation is given by .
Then if we have two different solutions and to our diophantine equation note that the difference will give use the following . This implies that we can obtain all solutions to the equation by determining one solution that satisfies and then add the general solution to the homogeneous problem.
We can find a solution to by using Euclid’s extended algorithm. Using Euclid’s extended algorithm we can find a solution to the equation . Then since we assumed to be a multiple of the we can write for some integer . Hence for we have is a solution to our diophantine equation and we conclude that all solutions are given by .
We can further generalize this to systems of linear diophantine equations. Using matrix notation, any system of diophantine equations can be written in the form . Here is an matrix of constants, is an dimensional column vector of constants and is an dimensional column vector of unknown variables. Then similar to linear algebra we can find a decomposition of the matrix over the integers. Here we can write where and are square matrices that are invertible over the integers and of correct sizes. Here, is a diagonal matrix with the elementary divisors on its diagonal. Since both and are invertible over the integers we find that . Note that we cannot solve for directly since is not invertible over the integers. However, relabeling and gives us linear equations of the form which can easily be solved. This does not guarantee a solution of our original problem. Note that is a solution if and only if for some vector that satisfies .
In econometrics we might also come across some systems of linear diophantine equations. A good example of this can be found in operations research. In operations research you sometimes have a linear constraint optimization problem where the variables can only take on integer values. These are in fact systems of linear diophantine equations if the constraints must hold with equality.
Fermat’s last theorem
Fermat’s last theorem is a very famous theorem in mathematics. The theorem states that there are no solutions to the diophantine equation given by for any . This seems like a very strange result since we have infinitely many solutions when . Showing that this equation has no solutions was however an incredibly difficult task as it took mathematicians over 350 years to prove the theorem that Fermat had conjectured to be correct. Since the proof is too complex for this article click this link for a complete proof. As a final note, there are values for and that come relatively close to being a solution. An example of this is which is relatively close but still wrong by a factor of .