Vieta Jumping

Why This Matters

Vieta jumping is a proof technique for Diophantine equations (see number theory and ML for broader connections) that appears simple once you see it but is difficult to discover independently. It became famous through IMO 1988 Problem 6, which stumped nearly every competitor. The technique is narrow in scope (it applies to specific types of equations) but powerful when applicable, and it illustrates a general principle: exploit the algebraic structure of quadratics to navigate the solution space.

Mental Model

You have an equation $f(a, b) = 0$ (or an inequality) involving two positive integers $a$ and $b$. Fix $b$ and view the equation as a quadratic in $a$. If $(a, b)$ is a solution, then $a$ is a root of this quadratic. By Vieta's formulas, the other root $a'$ satisfies $a + a' = -B/A$ and $a \cdot a' = C/A$ where $Aa^2 + Ba + C = 0$. Since $B$ and $C$ are integer expressions in $b$, the other root $a'$ is also an integer. If $a' > 0$, you have a new solution $(a', b)$ and can repeat. If $a' \leq 0$, you have reached a base case that can be analyzed directly.

Formal Setup

Definition

Vieta Jumping (Standard Form)

Given a Diophantine equation $f(a, b) = 0$ that is quadratic in $a$ (when $b$ is fixed):

$A(b) \cdot a^2 + B(b) \cdot a + C(b) = 0$

If $(a_0, b)$ is a positive integer solution, then Vieta's formulas give the second root:

$a_0 + a_1 = -\frac{B(b)}{A(b)}, \qquad a_0 \cdot a_1 = \frac{C(b)}{A(b)}$

The jump replaces $a_0$ with $a_1 = -B(b)/A(b) - a_0$. If $A(b)$ divides $B(b)$ and $C(b)$ in the integers, then $a_1$ is an integer.

The Method Step by Step

1. Assume for contradiction (or assume a minimal counterexample). Suppose $(a, b)$ is a solution with $a + b$ minimal (or $a$ maximal, depending on the problem).

2. Fix one variable. Hold $b$ fixed and write the equation as a quadratic in $a$.

3. Apply Vieta's formulas. The current value $a$ is one root. Compute the other root $a' = -B(b)/A(b) - a$.

4. Check integrality. Verify that $a'$ is an integer. This usually follows from the equation's structure.

5. Check positivity. Show $a' \geq 0$. Use the product of roots: $a \cdot a' = C(b)/A(b)$. If $C(b)/A(b) > 0$, then $a'$ has the same sign as $a$.

6. Obtain contradiction or base case. Show $a' < a$ (so the new solution is "smaller"), contradicting minimality. Or show $a' = 0$ and analyze this case directly.

Main Theorem

Proposition

Vieta Jumping Produces Integer Solutions

Statement

Let $f(a, b) = A(b)a^2 + B(b)a + C(b) = 0$ where $A$, $B$, $C$ are integer-valued functions. If $(a_0, b_0)$ is a positive integer solution and $A(b_0) \neq 0$, then the second root of $f(\cdot, b_0) = 0$ is the integer:

$a_1 = \frac{-B(b_0)}{A(b_0)} - a_0$

Moreover, $a_0 \cdot a_1 = C(b_0)/A(b_0)$.

Intuition

A monic quadratic with integer coefficients and one integer root must have another integer root. This is because the sum and product of roots equal integer quantities (by Vieta's formulas). Vieta jumping exploits this: every integer root has an integer partner. The descent structure has a flavor similar to the iterative refinement in Newton's method, where one solution generates the next.

Failure Mode

The technique fails if the equation is not quadratic in either variable, if $A(b) = 0$ for the relevant $b$ values, or if the second root is not guaranteed to be positive (in which case the descent argument may not work, though the base case $a' \leq 0$ might still be useful).

Canonical Example: IMO 1988 Problem 6

Example

IMO 1988 Problem 6

Problem. 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 a perfect square.

Setup. Let $k = \frac{a^2 + b^2}{ab + 1}$. We must show $k$ is a perfect square. Rearrange: $a^2 + b^2 = k(ab + 1)$, or equivalently:

$a^2 - kb \cdot a + (b^2 - k) = 0$

This is a quadratic in $a$ with $A = 1$, $B = -kb$, $C = b^2 - k$.

Vieta jump. If $(a, b)$ is a solution, the other root is $a' = kb - a$, and $a \cdot a' = b^2 - k$.

Descent. Assume $(a, b)$ is a solution with $a + b > 0$ minimal and $a \geq b$. The other root satisfies $a' = kb - a$ and $a \cdot a' = b^2 - k$. Since $k > 0$ and $a > 0$, if $a' > 0$ then $a' = (b^2 - k)/a$. We can show $a' < a$ (using $a \geq b$ and the structure of the equation), contradicting minimality unless $a' = 0$.

Base case. If $a' = 0$, then $b^2 - k = 0$, so $k = b^2$, a perfect square. This completes the proof.

When the Technique Applies

Vieta jumping works when:

• The equation is quadratic (or can be made quadratic) in one of its variables.
• The coefficients ensure integer second roots.
• A descent argument is available (the new solution is "smaller" in some sense).
• The base case is tractable.

It does not work for equations that are cubic or higher in both variables, equations where the second root is irrational, or problems where no natural descent ordering exists.

Common Confusions

Watch Out

The descent direction matters

You must choose which variable to fix and which to jump carefully. In the IMO 1988 problem, fixing $b$ and jumping in $a$ works when $a \geq b$. Fixing the wrong variable may produce a second root that is larger, not smaller, giving no contradiction.

Watch Out

Vieta jumping is not infinite descent

Infinite descent proves that no positive integer solutions exist. Vieta jumping reduces to a base case that does have solutions. The conclusion is different: Vieta jumping shows that all solutions arise from a known base case via jumping, not that no solutions exist.

Exercises

ExerciseCore

Problem

Let $a$ and $b$ be positive integers satisfying $a^2 + b^2 = 3ab - 1$. Fix $b$ and write this as a quadratic in $a$. Find the second root $a'$ in terms of $a$ and $b$. Verify that $a \cdot a' = b^2 + 1$.

Hint

Reveal Solution

ExerciseAdvanced

Problem

Use Vieta jumping to show that if $a$ and $b$ are positive integers with $a^2 + b^2 = 3ab - 1$, then the only solutions are $(a, b) \in \{(1, 1), (1, 2), (2, 1), (2, 5), (5, 2), (5, 13), (13, 5), \ldots\}$, forming a sequence related to Fibonacci numbers.

Hint

Reveal Solution

References

Canonical:

• Engel, Problem-Solving Strategies (1998), Chapter 6
• Andreescu & Enescu, Mathematical Olympiad Treasures (2011), Chapter 2

Current:

• Art of Problem Solving Wiki, Vieta Jumping

• Munkres, Topology (2000), Chapter 1 (set theory review)