In number theory, Vieta jumping, also known as root flipping, is a proof technique. It is most often used for problems in which a relation between two integers is given, along with a statement to prove about its solutions. In particular, it can be used to produce new solutions of a quadratic Diophantine equation from known ones. There exist multiple variations of Vieta jumping, all of which involve the common theme of infinite descent by finding new solutions to an equation using Vieta's formulas.
History
Vieta jumping is a classical method in the theory of quadratic Diophantine equations and binary quadratic forms. For example, it was used in the analysis of Markov equation back in 1879 and in the 1953 paper of Mills.
In 1988, the method came to the attention to mathematical olympiad problems in the light of the first olympiad problem to use it in a solution that was proposed for the International Mathematics Olympiad and assumed to be the most difficult problem on the contest:
Let and be positive integers such that divides . Show that is the square of an integer.
Arthur Engel wrote the following about the problem's difficulty:
Among the eleven students receiving the maximum score for solving this problem were Ngô Bảo Châu, Ravi Vakil, Zvezdelina Stankova, and Nicușor Dan. Emanouil Atanassov (from Bulgaria) solved the problem in a paragraph and received a special prize.
Standard Vieta jumping
The concept of standard Vieta jumping is a proof by contradiction, and consists of the following four steps: Assume toward a contradiction that some solution () exists that violates the given requirements. Take the minimal such solution according to some definition of minimality. Replace some by a variable x in the formulas, and obtain an equation for which is a solution. Using Vieta's formulas, show that this implies the existence of a smaller solution, hence a contradiction.
Example
Problem #6 at IMO 1988: Let and be positive integers such that divides . Prove that is a perfect square. Fix some value that is a non-square positive integer. Assume there exist positive integers for which . Let be positive integers for which and such that is minimized, and without loss of generality assume . Fixing , replace with the variable to yield . We know that one root of this equation is . By standard properties of quadratic equations, we know that the other root satisfies and . The first expression for shows that is an integer, while the second expression implies that since is not a perfect square. From it further follows that , and hence is a positive integer. Finally, implies that , hence , and thus , 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. For all above a certain base case, show that and that is an integer. Thus, while maintaining the same , we may replace with and repeat this process until we arrive at the base case. Prove the statement for the base case, and as has remained constant through this process, this is sufficient to prove the statement for all ordered pairs.
Example
Let and be positive integers such that divides . Prove that . If dividing implies that divides 1, and hence the positive integers , and . So, without loss of generality, assume that . For any satisfying the given condition, 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 and they are both integers, , and hence ; As long as , we always have , and therefore . Thus, while maintaining the same , we may replace with and repeat this process until we arrive at the base case. The base case we arrive at is the case where . For to satisfy the given condition, must divide , which implies that divides 2, making either 1 or 2. The first case is eliminated because . In the second case, . As has remained constant throughout this process of Vieta jumping, this is sufficient to show that for any satisfying the given condition, will always equal 3.