Diophantine equations
Diophantine equations

December 16, 2021

Share this article:

[supsystic-social-sharing id='1']

In mathematics we usually consider functions and equations over the real numbers. This means that we can input numbers like pi, e and sqrt{2} 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. 

Pythagorean triples

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 a^2 + b^2 = c^2. This is a polynomial equation with 3 unknowns a,b,c. 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 3^2 + 4^2 = 5^2. But it turns out that there are infinitely many primitive Pythagorean triples. Now what do I mean by primitive? Primitive means that a, b, c 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 (3, 4, 5) is a solution gives us all solutions of the form alpha(3, 4, 5) for any integer alpha since (3alpha)^2 + (4alpha)^2 = alpha^2 (3^2 + 4^2) = alpha^2 5^2 = (5 alpha)^2

One final thing that is interesting is Euclid’s formula for generating primitive Pythagorean triples. Euclid’s formula states that for positive integers m, n such that n < m, we have that (m^2 - n^2, 2mn, m^2 + n^2) is a Pythagorean triple and therefore a solution to our diophantine equation. To see this note that (m^2 - n^2)^2 + (2mn)^2 = m^4 - 2n^2m^2 + n^4 + 4n^2m^2 = m^4 + 2n^2m^2 + n^4 = (m^2 + n^2)^2 prove the fact that this is indeed a solutions. Note however that if both m and n 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 ax + by = c where a, b, c are integer and constant and x, y are variables. Then using Bézout’s identity one can show that this equation has infinitely many solutions over the integers if gcd(a, b) | c. This means that c must be a multiple of the greatest common divisor of a and b. Then the question is how we can find these solutions. First note that a homogenous solution to the equation is given by x = b and y = -a since ab - ba = 0. Then note that the smallest integer solution must be given by x = b / d and y = - a / d where d = gcd(a, b) to ensure that x, y will still be integers. Hence the general solution of the homogeneous equation is given by (alpha b / d, - alpha a / d)

Then if we have two different solutions (x_1, y_1) and (x_2, y_2) to our diophantine equation note that the difference will give use the following a (x_1 - x_2) + b (y_1 - y_2) = c - c = 0. This implies that we can obtain all solutions to the equation by determining one solution that satisfies ax + by = c and then add the general solution to the homogeneous problem. 

We can find a solution to ax + by = c by using Euclid’s extended algorithm. Using Euclid’s extended algorithm we can find a solution (x*, y*) to the equation ax + by = gcd(a, b). Then since we assumed c to be a multiple of the d = gcd(a, b) we can write c = kd for some integer k. Hence for (k x*, k y*) we have a(k x*) + b(k y*) = k (ax* + by*) = k d = c is a solution to our diophantine equation and we conclude that all solutions are given by (k x* + alpha b / d, k y* - alpha a / d).

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 Ax = c. Here A is an m \times n matrix of constants, c is an m dimensional column vector of constants and x is an n dimensional column vector of unknown variables. Then similar to linear algebra we can find a decomposition of the matrix A over the integers. Here we can write B = UAV where U and V are square matrices that are invertible over the integers and of correct sizes. Here, B is a diagonal matrix with the elementary divisors on its diagonal. Since both U and V are invertible over the integers we find that BV^{-1}x = Uc. Note that we cannot solve for x directly since B is not invertible over the integers. However, relabeling y = V^{-1}x and d = Uc gives us n linear equations of the form b_{i,i}y_i = d_i which can easily be solved. This does not guarantee a solution x of our original problem. Note that x is a solution if and only if x = Vy for some vector y that satisfies By = D

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 a^n + b^n = c^n for any n > 2. This seems like a very strange result since we have infinitely many solutions when n = 2. 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 a, b, c and n that come relatively close to being a solution. An example of this is  3987^{12} + 4365^{12} = 4472^{12} which is relatively close but still wrong by a factor of 10^33

Read more

Regression analysis: A beginner’s guide

Regression analysis: A beginner’s guide

Econome­­trics, the int­­ersection of economics and statistics, employs sophisticated methods to analyse and quantify relationships within economic systems. One of its fundamental tools is regression analysis, a statistical technique that allows economists tot model...

Are you tying your shoelaces wrong?

Are you tying your shoelaces wrong?

We tie our shoelaces to ensure that our shoes stay on tight, and we do these by tying a knot. There are different ways to tie your shoelaces, you may have learnt the “around the tree” technique, but somehow, they still always come undone, why? This all has to do with...