Vieta jumping

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 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.

History[]

Vieta jumping is a technique to produce new solutions of a Diophantine equation from known ones. It is a classical technique in the theory of quadratic Diophantine equations. It came to the attention to 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 contest:^[1][2]

Let a and b be positive integers such that ab + 1 divides a² + b². Show that ${\displaystyle {\frac {a^{2}+b^{2}}{ab+1}}}$ is the square of an integer.^[3]

Arthur Engel wrote the following about the problem's difficulty:

Nobody of the six members of the Australian problem committee could solve it. Two of the members were husband and wife George and Esther Szekeres, 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.

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.^[4] Emanouil Atanassov (from Bulgaria) solved the problem in a paragraph and received a special prize.^[5]

Standard Vieta jumping[]

The concept of standard Vieta jumping is a proof by contradiction, and consists of the following three steps:^[6]

1. Assume toward a contradiction that some solution exists that violates the given requirements.
2. Take the minimal such solution according to some definition of minimality.
3. Show that this implies the existence of a smaller solution, hence a contradiction.

Example

Problem #6 at IMO 1988: Let a and b be positive integers such that ab + 1 divides a² + b². Prove that a² + b²/ab + 1 is a perfect square.^[7][8]

1. Fix some value k that is a non-square positive integer. Assume there exist positive integers (a, b) for which k = a² + b²/ab + 1.
2. Let (A, B) be positive integers for which k = A² + B²/AB + 1 and such that A + B is minimized, and without loss of generality assume A ≥ B.
3. Fixing B, replace A with the variable x to yield x² – (kB)x + (B² – k) = 0. We know that one root of this equation is x₁ = A. By standard properties of quadratic equations, we know that the other root satisfies x₂ = kB – A and x₂ = B² – k/A.
4. The first expression for x₂ shows that x₂ is an integer, while the second expression implies that x₂ ≠ 0 since k is not a perfect square. From x₂² + B²/x₂B + 1 = k > 0 it further follows that x₂ is a positive integer. Finally, A ≥ B implies that x₂ = B² − k/A < A and thus x₂ + B < A + B, which contradicts the minimality of A + B.

Constant descent Vieta jumping[]

The method of constant descent Vieta jumping is used when we wish to prove a statement regarding a constant k having something to do with the relation between a and b. Unlike standard Vieta jumping, constant descent is not a proof by contradiction, and it consists of the following four steps:^[9]

1. The equality case is proven so that it may be assumed that a > b.
2. b and k are fixed and the expression relating a, b, and k is rearranged to form a quadratic with coefficients in terms of b and k, one of whose roots is a. The other root, x₂ is determined using Vieta's formulas.
3. It is shown that for all (a, b) above a certain base case, 0 < x₂ < b < a and that x₂ is an integer. Thus we may replace (a, b) with (b, x₂) and repeat this process until we arrive at the base case.
4. The statement is proven for the base case, and as k has remained constant through this process, this is sufficient to prove the statement for all ordered pairs.

Example

Let a and b be positive integers such that ab divides a² + b² + 1. Prove that 3ab = a² + b² + 1.^[10]

1. If a = b, a² must divide 2a² - 1 and thus a = b = 1 and 3(1)(1) = 1² + 1² + 1. So, without loss of generality, assume that a > b.
2. Let k = a² + b² + 1/ab and rearrange and substitute to get x² − (kb) x + (b² + 1) = 0. One root to this quadratic is a, so by Vieta's formulas the other root may be written as follows: x₂ = kb − a = b² + 1/a.
3. The first equation shows that x₂ is an integer and the second that it is positive. Because a > b, x₂ = b² + 1/a < b as long as b > 1.
4. The base case we arrive at is the case where b = 1. For this to satisfy the given condition, a must divide a² + 2, making a either 1 or 2. The first case is eliminated because a = b. In the second case, k = a² + b² + 1/ab = 6/2 = 3. As k has remained constant throughout this process, this is sufficient to show that k will always equal 3.

Geometric interpretation[]

Vieta jumping can be described in terms of lattice points on hyperbolas in the first quadrant.^[1] 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:

1. 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.
2. Prove the desired statement for the intersections of the hyperbolas and the line y = x.
3. 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.
4. It is shown that this process produces lower points on the same branch and can be repeated until some condition (such as x = 0) is achieved. Then by substitution of this condition into the equation of the hyperbola, the desired conclusion will be proven.

Example

This method can be applied to problem #6 at IMO 1988: Let a and b be positive integers such that ab + 1 divides a² + b². Prove that a² + b²/ab + 1 is a perfect square.

1. Let a² + b²/ab + 1 = q and fix the value of q. If q = 1, q is a perfect square as desired. If q = 2, then (a-b)² = 2 and there is no integral solution a, b. When q > 2, the equation x² + y² − qxy − q = 0 defines a hyperbola H and (a,b) represents an integral lattice point on H.
2. If (x,y) is an integral lattice point on H with x = y > 0, then one can see that q = 1 (with x = y = 1). This proposition's statement is true for this point.
3. Let P = (x, y) be a lattice point on a branch H with x, y > 0. By the previous remark, we can assume x ≠ y . By symmetry, we can assume that x < y and that P is on the higher branch of H. By applying Vieta's Formulas, (x, qx − y) is a lattice point on the lower branch of H. Let y′ = qx − y. From the equation for H, one sees that 1 + x y′ > 0. Since x > 0, it follows that y′ ≥ 0. Hence the point (x, y′) is in the first quadrant. By reflection, the point (y′, x) is also a point in the first quadrant on H. Moreover from Vieta's formulas, yy′ = x² - q, and y′ = x² - q/ y. Combining this equation with x < y, one can show that y′ < x. The constructed point Q = (y′, x) is in the first quadrant, on the higher branch of H with a smaller y-coordinate than the point P we started with.
4. This process can be repeated whenever the point Q has a positive x-coordinate. However, since the y-coordinates of these points will form a decreasing sequence of positive integers, it can only be repeated finitely many times. Thus, this process must arrive at a point Q = (0, x) on the upper branch of H; by substitution, q = x² is a square as required.

See also[]

• Vieta's formulas
• Proof by contradiction
• Infinite descent
• Markov number
• Apollonian gasket

Notes[]

External links[]

• Vieta Root Jumping at Brilliant.org