Vieta Root Jumping
Vieta jumping is a nickname for a particular kind of descent method that has become quite popular in higher level math Olympiad number theory problems. Like other instances of descent, it occurs when you have to solve a Diophantine equation (or system of equations, congruences or inequalities) whose solutions have some recursive structure. It is important to understand that Vieta jumping is not a technique that you can choose to use or not to use: most Vieta jumping problems can only be solved by Vieta jumping (else would require a tremendous amount of work).
The method of Vieta jumping, also known as root flipping, can be very useful in problems involving divisibility of positive integers. The idea is to assume the existence of a solution for which the statement in question is wrong, and then to consider the given relation as a quadratic equation in one of the variables. Using Vieta’s formula, we can display a second solution to this equation. The next step is to show that the new solution is valid and smaller than the previous one. Then by the argument of infinite descent or by assuming the minimality of the first solution, we get a contradiction.
It is a relatively new proof technique in solving mathematical Olympiad problems, and the first appearance is at the 1988 International Mathematical Olympiad.
How to Recognize
Vieta Jumping is just a particular instance of a more general method of descent, so don't be surprised if the solutions in your problem have a more complicated recursive structure. The tell-tale sign of Vieta jumping is the existence of a lemma (similar in spirit to the one below), which gives a relationship between different possible solutions. Look for a symmetric equation or congruence that has degree two in each of the two variables. (Note that there may also be other "parameter" variables in the problem.) Once such a lemma is recognized and established, you should look for some inequalities that will tell you in what direction to jump.
Usually, the lemma will say something along the lines of "if is a solution for some constraint, then is also a solution for the same constraint." This constraint is usually given by fixing one or more of the variables.
In the case of a quadratic, we can consider one such as
which is a quadratic in terms of . We know the properties of quadratics, i.e. there are always two solutions. Hence, if we fix and let , then we are left with
And we can use Vieta's formula (hence the name) to get a relationship between the two solutions. One we already know is , and the other (call it ) gives us and .
Upon showing this relationship, it is generally helpful to look for ways to constrain the values of , such as by letting a relationship between and dictate another relationship between and and seeing where that goes.
The end goal depends on the problem, but will usually result in you being able to restrict the values you need to search down to a few numbers, or in other cases show a contradiction if conditions (what the problem is asking to prove) aren't met.
The Vieta root jumping technique allows you to approach problems like this:
1988 IMO Example
Perhaps the earliest Vieta jumping problem was Problem 6 at the 1988 International Mathematical Olympiad. At the time, it was widely recognized as both beautiful and exceedingly hard (dubbed "The Legend of Question #6"), because the technique of Vieta jumping was not widely used.
(IMO1988/6)
Let and be positive integers such that divides Show that is a perfect square.
Suppose Then for a fixed the set of solutions has a very interesting structure, described by the following lemma:
Lemma:
Suppose is a positive integer solution of the equation Then also is a solution.
Proof of lemma:
Consider the quadratic equation We get this equation by fixing and replacing with .
For a given solution , we know that is a root of the above equation. By Vieta (sum of roots), we know that the other root is , which is an integer. Using the product of roots, the other root can be written as .
If let the other root be . We have If then which contradicts being the root of the equation. If then so is a perfect square and we are done. Otherwise, we can keep going, using instead of . We get a decreasing sequence of positive integers so that for all the pair satisfies Clearly, this sequence cannot continue indefinitely, so at some point one of the numbers will become proving that is a perfect square.
The infinite sequence as above is what distinguishes Vieta jumping from other descent methods. Note that each consecutive pair is a solution, and and are two roots of a quadratic equation that involves . The condition must be symmetric and the sequence must be in some sense decreasing, so the sequence must terminate. Note also that Vieta jumping works both ways: one can recover all solutions from the terminal ones by "jumping back."
Worked Examples
Let and be positive integers such that . Show that .
We see that , and are solutions. This suggests that the solutions are related to each other by Vieta root jumping.
If , then we have , and thus . Otherwise, suppose that is a solution. Let .
Consider the following quadratic equation Then, we know that would be a solution to this quadratic equation, and the other solution is . Since , it is an integer. Since , we get a smaller solution .
Hence, starting with any solution , we can always backtrack along it until . This gives us , or that . Hence, or 2.
The value of stays the same throughout. We can calculate that if , we get , and if we still get . Hence, we must always have , or that .
(Crux Mathematicorum)
Suppose and are positive integers such that Show that is a perfect square.
Suppose For fixed and consider all positive integer pairs such that Then this set has recursive structure given by the following lemma:
Lemma:
Suppose satisfies the equation and . Then also satisfies the equation where is plugged in for and is plugged in forProof of lemma:
The equation has as one of its roots. Because cannot be and by Vieta's formula the other root isNow suppose is not a perfect square. Staring from with we will apply the lemma. Note that cannot be negative, otherwise we get a contradiction: Since is not a perfect square, cannot be so Also, We can continue and get an infinite decreasing sequence which is impossible. Therefore, must be a perfect square.
Find the number of pairs of non-negative integers such that , , and .
We will first prove the following lemma:
Lemma:
Suppose the pair is such that , , and .
Then the pair satisfies the conditions , , and .Proof of lemma:
The first two conditions are obvious. To prove the third one, note that and , and thus .Now starting from any pair satisfying the condition above, we apply the lemma several times, producing smaller and smaller pairs, until we get to a pair for some . Note that the above construction can be uniquely reversed: the pair is obtained from a pair by setting . So we can generate all pairs satisfying the conditions of the problem from pairs for . Specifically,
.Overall, we get pairs with , plus pairs with , plus other pairs, for a grand total of pairs.
(IMO 2007/5)
Let and be positive integers such that . Show that .
It is hard to see how to apply Vieta's formula directly, since there is no easy way to "jump" from solution to . The question suggests that would be an important quantity to consider.
Suppose that satisfies the conditions with . Observe that Fix . We want to consider all positive integer solutions to . Let be the solution pair which minimizes the sum of both values. Since the equation is symmetric, we may assume that .
Consider the quadratic equation It has 2 roots, namely and . By the minimality of , we get that , or that . So , which is a contradiction.
Hence, this shows that no solution of distinct integers is possible.
If and are positive integers such that is an integer, then .
Lemma 1:
Suppose a certain pair of integers is a solution to the equation . Then I say the pair is also an integer solution.Proof:
Consider the equation . By assumption, is one of the roots. Therefore, by Vieta's formulas, the other root is . By substituting the formula for , this equals . We already know that the numerator is divisible by (since is an integer), and it's clearly also divisible by . Since , the numerator is also divisible by . Hence the new root is an integer. Hence, is also an integer solution to the equation.Lemma 2:
If , then .Proof:
Since , it follows that . Therefore, Hence .Now, let be the solution to such that the value of is minimized (but nonnegative). Then, by Lemmas 1 and 2, we must have , otherwise it is possible to get a smaller value of .
- If , then .
- If , then . Then and therefore respectively.
- If , then we have . Thus . Hence, is a factor of 17. Therefore , and therefore .
Therefore, the maximum possible value of in any of these cases is 5.
Ariel Gershon
See this problem.
Additional Problems
1) Find all pairs of integers such that is also an integer.
2) [Vietnam 2002] Find all positive integers for which the equation has a solution in positive integers.
Hint: Focus on the smallest solution and compare it to another solution to get a bound on .
3) [Putnam 1933] Prove that for every real number , the equation
has a solution in which are all integers greater than .
4) [Sam Vandervelde] Let be positive integers such that . Then, can be written as the sum of 2 positive squares.
Note: This generalizes to 4 or more variables. However, Lagrange 4-square theorem tells us that the case of 5 or more variables doesn't produce a meaningful condition.
5) Determine all pairs of positive integers such that is a positive integer.
6) [Calvin Lin] Show that the only positive integer solutions to and is .
Hint: Proceed as per usual to construct the family of solutions, and show that they are all the same.