Question number six: Vieta jumping



October 17, 2016

Share this article:

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 $a$ and $b$ be positive integers such that $ab + 1$ divides $a^2 + b^2$ . Show that $\frac{a^{2}+b^2}{ab+1}$ is the square of an integer.
The first thing to notice is that $a,b \in \mathbb{N}$ . 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, $a$ equals 1 and $b$ 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 $b$ . 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 $(0,b)$ and $(a,0)$ for any $a,b \in \mathbb{N}$ . Still, this is not enough.
After computing the solutions for $a$ and $b$ between zero and eight. The points $(2, 2^3)$ and $(2^3,2)$ are found. If we plug this into the formula we obtain the following result.
$\frac{a^2+b^2}{ab+1}=\frac{2^2+(2^3)^2}{2\cdot 2^3+1}=\frac{2^2(1+2^4)}{2^4+1}=2^2$
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 $(0,2), (2,0), (2,8)$ and $(8,2)$ fit well in the equation, $\frac{a^2+b^2}{ab+1}=2^2=4$ , that is connected to the graph below.

Here $b$ is plugged in on the y-as and $a$ on the x-as. It is obvious that $a$ and $b$ 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 $a$ is 2 we find the line going through $b$ is 0 and $b$ 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 $(A,B)$ with respect to some function of $A$ and $B$ , usually $A+B$ , is taken. The equation is then rearranged into a quadratic with coefficients in terms of $B$ , one of whose roots is $A$ , 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 $(A,B)$ 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 $a$ and $b$ be positive integers such that $ab + 1$ divides $a^2 + b^2$ . Show that $\frac{a^{2}+b^2}{ab+1}$ is the square of an integer.
Let $k = \frac{a^{2}+b^2}{ab+1}$ . 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 $k$ , let $(A,B)$ be the solution of the equation that minimizes the value of $A+B$ and without loss of generality $A \geq B$ . We can rearrange the equation and replace $A$ with a variable $x$ to yield $x^2 - (kB)x + (B^2 - k) = 0$ .One root of this equation is $x_1 = A$ . By Vieta’s formulas, the other root may be expressed in the following two ways: $x_2 = kb - A$ and $x_2 = \frac{B^2 - k}{A}$ .
The first expression for $x_2$ shows that $x_2$ is an integer, while the second implies that $x_2 \neq 0$ . From $\frac{x_2^2 = B^2}{x_2 B +1} = k > 0$ it further follows that $x_2$ is positive. Finally, A ≥ B implies that $x_2 = \frac{B_2-k}{A} < A$ and thus $x_2 + B < A + B$ , which contradicts the minimality of $(A,B)$ .

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 $x$ and $y$ so that they are symmetric about the line $y=x$ .
Prove the desired statement for the intersections of the hyperbolas and the line $y=x$ .
Assume there is some lattice point $(x,y)$ on some hyperbola and without loss of generality $x<y$ . 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 $y=x$ 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 $x=o$ ) 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 $q = \frac{a^{2}+b^2}{ab+1}$ and fix the value of q. Then $(a,b)$ represents a lattice point on the hyperbola H defined by the equation $x_2 + y_2 - qxy -q = 0$ .
If $x=y$ then we find $x=y=q=1$ , which trivially satisfies the statement.
Let $(x,y)$ be a lattice point on a branch $H$ , and assume $x<y$ so that it is on the higher branch. By applying Vieta’s Formulas, $(x, qx - y)$ is a lattice point on the lower branch of $H$ . Then, by reflection $(qx - y, x)$ 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 $y=x$ .
This process can be repeated. From the equation of $H$ , it is not possible for this process to move into the second quadrant. Thus, this process must terminate at $x=0$ and by substitution, $q = y_2$ 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

← Previous: Hoe je Wie is het? bijna altijd kan winnen Next: Memories from Greece →

Infinite Hotel Paradox

by Joep Nieuwenburg | Sep 29, 2023 | Education, Mathematics

Suppose you have a hotel with infinitely many occupied rooms. Now another guest shows up, what would you do? It turns out that you can still accommodate him. In fact, you can actually accommodate a bus of infinitely many guests and even infinite busses of infinitely...

The Sausage Catastrophe

by Bart Koopmans | Sep 20, 2023 | Mathematics

Introduction Contrary to what you might expect, this article is not actually about sausages. It is not even about food at all. Instead, the sausage catastrophe is a mathematical phenomenon that occurs when studying the theory of finite sphere packing. Finite...

The Seven Bridges of Königsberg

by Otis de Waal | Jun 13, 2023 | Mathematics, Operations Research

Imagine you are taking a stroll around the 18th century Prussian city of Königsberg (currently Kaliningrad, Russia). The river Pregel runs through Königsberg and there are two large islands in this river. The islands are connected to each other and to the mainland by...

« Older Entries

Mathematics

October 17, 2016

Share this article:

Written by Anne Dumoulin