In 1988 the International Mathematical Olympiad (IMO) was held in Australia. In this particular year question number six was sent in by a West German mathematician. For a long time, this question has been one of the hardest math problems to solve. Not only was this problem extremely complicated, it also brought up a new theorem which is nowadays taught at Universities worldwide.
International Mathematical Olympiad
The International Mathematical Olympiad is a competition for pre-college students who all compete for their country in teams of up to six people. The paper sheet of the test contains six problems for which are given 90 minutes each on average. Annually, about 100 countries send in their teams including supervisors and coaches. The content ranges from subjects such as complex geometry to functional equations and number theory. In order to find the solutions, extensive knowledge of theorems is required. On the other hand calculus is never required, since it is assumed anyone with mathematical insights is capable of understanding these problems. Additionally, the puzzlers are designed to throw you off if you know high school maths too well. Therefore, in order to solve the problems one should look beyond their general knowledge. Contestants must be under the age of 20. This was not a problem for the thirteen-year-old Terence Tao, who participated at the IMO of 1988. He was one of the eleven students who succeeded to answer question number six perfectly. The other students did not receive any points at all for this question.
Problem number six
Each country may submit problems to a Problem Selection Committee that is provided by the host country. The host country itself is not allowed to hand in any suggestive problems. After six hours of trying to solve the question of the West German mathematician, no one had been able to find a suitable answer. Instead of throwing off the submission since it was too hard, the board decided to put the question in the test. Next to it they wrote down a double asterisks on the paper sheet, in view of that the students would know they should not break their heads on this one. The problem was formulated as follows:
Let and
be positive integers such that
divides
. Show that
is the square of an integer.
The first thing to notice is that . The equation could equal a fraction, nevertheless this does not matter for this problem. If it happens to be a whole number, and that number would also be a square, then we are looking at a solution of our problem. Picture yourself sitting in the exam hall during this question. Probably not knowing where to begin, the first thing one would do is simply plug in numbers. It is easy to start small, for instance,
equals 1 and
equals 2, this gives us a fraction, namely 5 over 3. Now plug in a equals 0 and b equals 2, this gives 2 to the power 2. It this case it is clever to keep the answer in the square form. This enables us to see we are dealing with a solution. For now the point (0,2) is a solution. Now, when looking close at the equation, it follows quite obviously that for any point where a is zero, it would work for any sort of
. This also works the other way around if b is zero and the other numbers are positive integers. By this it can be concluded that there is an infinite number of solutions, namely
and
for any
. Still, this is not enough.
After computing the solutions for and
between zero and eight. The points
and
are found. If we plug this into the formula we obtain the following result.
It is now easy to see another infinite number of solutions is found. Looking at the obtained particular solutions combined gives us the following. The points and
fit well in the equation,
, that is connected to the graph below.
Here is plugged in on the y-as and
on the x-as. It is obvious that
and
can be swapped and therefore we have found these four solutions. Now some students who participated on the Olympiad saw that they connected every single answer by drawing parallel lines. For
is 2 we find the line going through
is 0 and
is 8, these are two solutions. The two answers are in fact connected by a parabola in the z-as. This concept is nowadays known as Vieta jumping.
Standard Vieta jumping
In number theory, Vieta jumping, also known as root flipping, is a proof technique. There are different methods known for this principle. In this article the standard Vieta jumping and the geometric interpretation are considered, applied on the IMO problem.
The concept of standard Vieta jumping is a proof by contradiction. It is assumed for contradiction that solutions to the given relation exist that do not satisfy the statement we wish to prove.
The minimal solution with respect to some function of
and
, usually
, is taken. The equation is then rearranged into a quadratic with coefficients in terms of
, one of whose roots is
, and Vieta’s formulas are used to determine the other root to the quadratic.
It is shown that the other root gives a solution that is both valid and smaller, by our previously determined definition, thus disproving the minimality of the solution and contradicting the existence of a solution for which the conclusion is false.
For question number six this results in the following proof of Vieta jumping. Let and
be positive integers such that
divides
. Show that
is the square of an integer.
Let . We assume that there exist one or more solutions to the given condition for which k is not a perfect square.
For a given value of , let
be the solution of the equation that minimizes the value of
and without loss of generality
. We can rearrange the equation and replace
with a variable
to yield
.One root of this equation is
. By Vieta’s formulas, the other root may be expressed in the following two ways:
and
.
The first expression for shows that
is an integer, while the second implies that
. From
it further follows that
is positive. Finally, A ≥ B implies that
and thus
, which contradicts the minimality of
.
Geometric interpretation of Vieta jumping
Vieta jumping can be described in terms of lattice points on hyperbolas in the first quadrant. The same process of finding smaller roots is used instead to find lower lattice points on a hyperbola while remaining in the first quadrant. The procedure is as follows:
From the given condition we obtain the equation of a family of hyperbolas that are unchanged by switching and
so that they are symmetric about the line
.
Prove the desired statement for the intersections of the hyperbolas and the line .
Assume there is some lattice point on some hyperbola and without loss of generality
. Then by Vieta’s formulas, there is a corresponding lattice point with the same x-coordinate on the other branch of the hyperbola, and by reflection through
a new point on the original branch of the hyperbola is obtained.
It is shown that this process produces lower points on the same branch and can be repeated until some condition (such as ) is achieved. Then by substitution of this condition into the equation of the hyperbola, the desired conclusion will be proven.
This method can be applied to problem 6. Let and fix the value of q. Then
represents a lattice point on the hyperbola H defined by the equation
.
If then we find
, which trivially satisfies the statement.
Let be a lattice point on a branch
, and assume
so that it is on the higher branch. By applying Vieta’s Formulas,
is a lattice point on the lower branch of
. Then, by reflection
is a lattice point on the original branch. This new point has smaller y-coordinate, and thus is below the original point. Since this point is on the upper branch, it is still above
.
This process can be repeated. From the equation of , it is not possible for this process to move into the second quadrant. Thus, this process must terminate at
and by substitution,
is a square as required.
Nowadays, Terence Tao focuses among other things such as harmonic analysis, partial differential equations and geometric combinatorics. Since 2015, he holds the James and Carol Collins chair in mathematics at the University of California, Los Angeles. Tao was a co-recipient of the 2006 Fields Medal and the 2014 Breakthrough Prize in Mathematics.
References
Vieta proofs: www.wikipedia.com/vietajumping, 2016
Dit artikel is geschreven door Anne Dumoulin