In mathematics, Vieta jumping, also known as root flipping, is a number theory proof technique. It is most often used for problems in which a relation between two positive integers is given, along with a statement to prove about its solutions. There are multiple methods of Vieta jumping, all of which involve the common theme of infinite descent by finding new solutions to an equation using Vieta's formulas.
Vieta jumping is a relatively new technique in solving mathematical olympiad problems, as the first olympiad problem to use it in a solution was proposed in 1988 for the International Mathematics Olympiad and assumed to be the most difficult problem on the test. Arthur Engel wrote the following about the problem difficulty:
Nobody of the six members of the Australian problem committee could solve it. Two of the members were George Szekeres and his wife, both famous problem solvers and problem creators. Since it was a number theoretic problem it was sent to the four most renowned Australian number theorists. They were asked to work on it for six hours. None of them could solve it in this time. The problem committee submitted it to the jury of the XXIX IMO marked with a double asterisk, which meant a superhard problem, possibly too hard to pose. After a long discussion, the jury finally had the courage to choose it as the last problem of the competition. Eleven students gave perfect solutions.
Standard Vieta jumping
- 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 forms 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.
1988 IMO #6. Let and be positive integers such that divides . Prove that is a perfect square.
- Let . We assume that there exist one or more solutions to the given condition for which is not a perfect square.
- For a given value of , let be the solution to this equation with the minimum value of and . 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 written as follows: .
- The first equation shows that is an integer and the second shows that it is nonzero (if it were zero, , but we have assumed that is not a perfect square). Also, cannot be less than zero, because that would imply that which implies that which implies that which is a contradiction. Finally, implies that which implies that which contradicts the minimality of .
Constant descent Vieta jumping
The method of constant descent Vieta jumping is used when we wish to prove a statement regarding a constant having something to do with the relation between and . Unlike standard Vieta jumping, constant descent is not a proof by contradiction, and it consists of the following four steps:
- The equality case is proven so that it may be assumed that .
- and are fixed and the expression relating , , and is rearranged to form a quadratic with coefficients in terms of and , one of whose roots is . The other root, is determined using Vieta's formulas.
- It is shown that for all above a certain base case, and that is an integer. Thus we may replace with and repeat this process until we arrive at the base case.
- The statement is proven for the base case, and as has remained constant through this process, this is sufficient to prove the statement for all ordered pairs.
Let and be positive integers such that divides . Prove that .
- If , must divide and thus and .
- So, assume . Let without loss of generality. Let and rearrange and substitute to get . One root to this quadratic is , so by Vieta's formulas the other root may be written as follows: .
- The first equation shows that is an integer and the second that it is positive. Because , as long as .
- The base case we arrive at is the case where . For this to satisfy the given condition, must divide , making either 1 or 2. The first case is eliminated because . In the second case, . As has remained constant throughout this process, this is sufficient to show that will always equal 3.
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 result 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 1988 IMO #6: Let and be positive integers such that divides . Prove that is a perfect square.
- Let , then we have the hyperbola . Call this hyperbola .
- If then we find .
- 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 with and by substitution, .
- Arthur Engel (1998). Problem Solving Strategies. Springer. p. 127. doi:10.1007/b97682. ISBN 978-0-387-98219-9.
- "Results of International Mathematical Olympiad 1988". Imo-official.org. Retrieved 2013-03-03.
- Yimin Ge (2007). "The Method of Vieta Jumping". Mathematical Reflections 5.
- "AoPS Forum - One of my favourites problems, yeah!". Artofproblemsolving.com. Retrieved 2013-03-03.
- "AoPS Forum — Lemur Numbers". Artofproblemsolving.com. Retrieved 2013-03-03.
- "AoPS Forum - x*y | x^2+y^2+1". ArtOfProblemSolving.com. 2005-06-07. Retrieved 2013-03-03.