Diophantine equations
Maybe the most familiar and important mathematical concept you meet in your math studies is equation. Mathematicians try to express the world in equations. Of course, there is no “World Equation”, but there are very famous equations which may have changed the world.
Maybe Einstein’s E=mc2 from physics should come into your mind. From mathematics you may remember the equation expressing the Pythagorean theorem, the relation between the lengths of the sides of a right triangle. You face the problem of solving equations at an early stage of your math studies. What does it mean to solve an equation?
Roughly speaking, an equation is an algebraic relation between different quantities, usually denoted by letters or by some other symbols. In the above equation of Einstein these are E, m and c. From pure mathematical point of view it makes no difference what these letters mean. We simply have three quantities with the property that multiplying one of them with the square of the second one we obtain the third quantity. Now in this case it is clear that any two of the three quantities uniquely determine the value of the third one. We have the same phenomenon with the Pythagorean equation: a2 + b2= c2. Given a and b we can compute c: we simply take the square root of the sum of the squares of a and b. But if a and c are given, then we also can compute b by the equally simple formula a2 – c2= b2: now we take square root from the difference of the squares of a and c.
The point is that if any number of quantities are related by an algebraic equation and all but one of them is known, then there is good hope that the remaining one can be determined, can be computed. In such cases there are some known quantities, and there is one unknown which is to be determined: the process how we determine it is the solution of the equation.
The ancient Greeks were masters of – among others – solving equations. Of course, for the applications it is very important to know the following things: 1) is there a solution? 2) is the solution unique? 3) how to find the solution(s) — in case the answer to the first question is “yep”.
In order to study these questions we have to set up some rules. First of all, we have to specify the domain of the equation, the collection of objects where we are looking for solutions. For instance, if we consider the Pythagorean equation in its original, geometric context, then the letters a,b,c denote the length of the sides of some triangle, hence they are “a priori” positive real numbers.
Nevertheless, the “solution process” mentioned above will provide also a negative solution, even if a,b are positive numbers. Indeed, taking square root from a positive real number gives two real numbers one of them being the negative of the other. This negative solution is fake in the sense that it cannot be the length of a side of the triangle, so it is definitely not the solution of the geometrical problem.
On the other hand, viewing the equation just in itself, independently of geometry this situation shows that an equation may have more than one solution even in the case if there is only one unknown. If there are more than one unknowns then we cannot expect that the solution is unique. For instance, if there is an equation which includes two unknowns then in most cases, we can give an arbitrary value to one of them and then the equation will determine the value of the remaining other unknown. Changing the arbitrary value may result in several, maybe even infinitely many different solutions.
In general, if you have some experience in solving different types of equations then you may have a suspicion: we can expect a unique solution in those cases only when the number of equations we consider simultaneously is equal to the number of unknowns in this system of equations. Although there are so many simple counterexamples to this “conjecture” that it is definitely far from being true but it still expresses some general “law of nature”: given some number of variables we cannot require them to satisfy more independent conditions than their number.
Their “degree of freedom” is roughly equal to their number.
In this spirit we classify equations depending on the number of unknowns and the simplest ones are the equations with one single unknown. You may have learned about linear and quadratic equations with one unknown: we have very simple, general solution methods for these types of equations and this field does not offer too much interest for us.
You may also have some experience with linear equation systems in two or more variables: they generally consist of two or more equations – in accordance with the above mentioned “degree of freedom” principle.
But math people are not robots: they ask non-standard questions: what if we have one linear equation with two unknowns? Well, as I told you, in this case we have infinitely many solutions, namely, we assign any value to one of the two variables, and then we have a unique solution of the linear equation in one variable obtained in this way. In this sense the problem is highly indeterminate. So, what is the question?
As I told above, ancient Greeks were very smart guys in math: they asked about linear equations in two variables, but they wanted to find whole numbers, AKA integers as solutions, only. So, the domain of the definition of the equation is restricted to the integers, all the unknowns and known numbers in the equation are integers. What is the difference?
Well, when solving a linear equation sometimes we need to divide and division may produce non-integers. So, this restriction may decrease the number of values which are candidates for being solution. The problem becomes less indeterminate.
The great master of such equations was Diophantus, the Greek, who lived approximately between 200 and 284, and a large class of such equations has been named after him: diophantine equations. The simplest ones are the linear diophantine equations in two variables having the general form: a x+b y=c, and here a,b,c are given integers, further we are looking for integer solutions x,y.
In fact, we may allow a,b,c to be rational numbers, because in that case multiplying the equation by the common denominator of the three numbers a,b,c we arrive at an equation with integer coefficients. Diophantine equations have a wonderful theory and I just want to raise your interest in this field by exhibiting some problems and methods in the subject.
Let me start with a simple example. In the News I wrote about the first math competition in Botswana, the BOTS50 Math Challenge which was held last year on the occasion of the 50th anniversary of the independence of the country. The problem sheet at that tournament consisted of 20 questions and the marking was as follows: correct answer 6 points, incorrect answer 0 point, skipped question 1.5 points. The best solver earned 91.5 points. Question: how many correct answers had the champion?
First of all let’s try to formulate this problem as an equation: suppose that Champ had x correct answers, y skipped questions and z incorrect solutions. Using the marking system this gives the equation: 6 x + 1,5 y=91,5. On the other hand, we obviously have the relation x+y+z=20 and the obvious condition that x,y,z are non-negative integers.
At this moment we have three unknowns and two equations, hence the problem seems to be indeterminate: the number of unknowns is greater than the number of conditions. Honestly, we have still an additional requirement about the non-negativity of the unknowns.
Let’s try to transform our problem to a diophantine equation. From the first equation we get 12 x+3 y=183, or 4 x+y=61, which gives y=61- 4 x. This must be non-negative, which means 4 x is at most 61, that is x is between 0 and 15,25.
Now we substitute into the second equation to get x+61-4x+z=20, or 3x-z=41, which gives z=3x-41. This is again non-negative, which means x is between 41/3 and 20. Together with the previous conditions for x we have that x is 14 or 15. We have then, respectively, that y is 5 or 1 and z is 1 or 4.
Finally, we have the following possibilities for the achievement of Champ: either she (…) solved 14 problems correctly for 84 points, skipped 5 questions for 7.5 points, and gave one wrong answer — this makes 91.5 points. The other possibility is that she gave 15 correct answers for 90 points, left 1 question unanswered for 1.5 points and she gave 4 incorrect solutions — the total score is 91.5 again.
Nice work Champ! And nice experience for us with a life-problem which leads to a diophantine equation even with additional restrictions and still can be handled.