Vieta Jumping

Why This Matters

Vieta jumping is the canonical descent technique for two-variable Diophantine problems with a hidden quadratic structure. It earned its place in the olympiad canon through its application to one of the hardest problems in the history of the International Mathematical Olympiad: IMO 1988 Problem 6.

The pattern: a problem fixes a relation $f(a, b) = k$ where $f$ is symmetric or quadratic in one variable. Vieta's formulas say that if $a$ is a root of a quadratic $x^2 - sx + p = 0$ (treating $b$ as fixed), then there is a second root $a' = s - a = p / a$ . The "jumped" pair $(a', b)$ also satisfies the original relation, and is often smaller than the original. Iterating this jump, you descend to a minimal pair where contradiction or base case lands.

Recognize Vieta jumping when:

The problem fixes a relation symmetric in two integers.
Treating one variable as fixed gives a quadratic in the other.
The relation is preserved when you swap one variable for $s - a$ or $p / a$ .
You suspect a minimal solution and want to descend.

This is the technique for the family of olympiad problems "prove $f(a, b)$ has property $P$ for all integer solutions."

The Setup

Suppose we have a relation $R(a, b) = k$ for integers $a, b \ge 1$ (or possibly $\ge 0$ depending on the problem). Fix $b$ and view $R(x, b) = k$ as a quadratic in $x$ :

$x^2 - s(b) x + p(b) = 0,$

where $s(b)$ and $p(b)$ are functions of $b$ and $k$ . By Vieta's formulas, the two roots $a_1, a_2$ satisfy:

$a_1 + a_2 = s(b), \qquad a_1 \cdot a_2 = p(b).$

If $a$ is one solution, the other root is:

$a' = s(b) - a = p(b) / a.$

The two formulas for $a'$ are equivalent (consistency check in any computation). Critically, if $a'$ is a positive integer, then $(a', b)$ is also a solution to the original problem, and we can descend.

IMO 1988 Problem 6: The Canonical Example

Theorem

IMO 1988 Problem 6

Statement

Let $a, b$ be positive integers such that $ab + 1$ divides $a^2 + b^2$ . Then $(a^2 + b^2) / (ab + 1)$ is a perfect square.

Intuition

The fraction $k = (a^2 + b^2)/(ab + 1)$ is some positive integer. The claim is that $k$ is a perfect square. The proof technique: assume $k$ is not a perfect square, take a counterexample $(a, b)$ minimizing $a + b$ , and Vieta-jump to a smaller counterexample, contradicting minimality.

Proof Sketch

Setup. Fix $k$ and consider the equation $\frac{a^2 + b^2}{ab + 1} = k$ , i.e., $a^2 + b^2 = k(ab + 1)$ , equivalently $a^2 - kba + b^2 - k = 0$ .

Treat this as a quadratic in $a$ with $b$ fixed. The two roots $a_1, a_2$ satisfy:

$a_1 + a_2 = kb, \qquad a_1 a_2 = b^2 - k.$

Descent. Suppose for contradiction that $k$ is not a perfect square, and choose a counterexample $(a, b)$ with $a + b$ minimal. WLOG $a \ge b$ .

The "jumped" partner of $a$ is $a' = kb - a = (b^2 - k)/a$ .

$a'$ is an integer. Both formulas give the same value; $a' = kb - a$ is an integer by construction.
$a' \ne 0$ . If $a' = 0$ , then $b^2 = k$ , contradicting our assumption that $k$ is not a perfect square.
$a' > 0$ . From $a' = (b^2 - k)/a$ : if $b^2 < k$ , then $a' < 0$ . We claim $b^2 \ge k$ : if $b^2 < k$ , then since $a \ge b$ , $a^2 + b^2 \ge 2 b^2$ but $k(ab + 1) \ge k \cdot 1 > 2b^2$ , so $k > 2b^2 \ge b^2 + 1$ , a quick check rules this out for small cases and a careful inequality handles the general case (see Engel for details). Conclusion: $b^2 \ge k > 0$ , so $a' > 0$ .
$a' < a$ . Since $a' = (b^2 - k)/a$ and we just argued $b^2 \ge k$ and $a \ge b$ , we have $a' \le b^2 / a \le a$ . Equality $a' = a$ would require $a = b$ and $b^2 = k$ , again a perfect square. So $a' < a$ .

Now $(a', b)$ is also a solution with $a' + b < a + b$ , contradicting minimality. Hence $k$ must be a perfect square.

Why It Matters

This problem was famously rated the hardest IMO 1988 problem, solved by only 11 of 268 contestants. The Vieta-jumping solution became the canonical reference for the technique. The same descent pattern applies to many later olympiad problems and shortlist problems through 2024.

Failure Mode

The argument requires:

The "jumped" value $a'$ is a positive integer (not zero, not negative).
$a'$ is strictly smaller than $a$ .

If either fails, the descent gets stuck. For instance, if $a' = a$ , you have a fixed point of the jump and cannot descend; this is the base case signal: usually, fixed points correspond to the answer to the problem.

report a correction →

The Recognition Cues

Vieta jumping applies when:

Cue	Example
Symmetric relation in two integers	$a^2 + b^2 = k(ab + 1)$
Quadratic in one variable when fixing the other	$a^2 - kba + (b^2 - k) = 0$
Vieta sum/product gives a "swapped" partner	$a' = kb - a$
Jumping shrinks a witness	$(a, b) \to (a', b)$ with $a' < a$
Suspected smallest counterexample to derive contradiction	by well-ordering on $\mathbb{N}$

When two of these line up, suspect Vieta jumping. The technique pairs naturally with the well-ordering principle (every non-empty subset of $\mathbb{N}$ has a least element) and infinite descent (Fermat's classic technique).

Worked Example: The Markov Triple Equation

Example

Markov triples (1879)

Show that any positive-integer solution $(a, b, c)$ to $a^2 + b^2 + c^2 = 3abc$ can be reached from $(1, 1, 1)$ by a sequence of "Markov moves" $(a, b, c) \to (3bc - a, b, c)$ .

Solution sketch. Fix $b, c$ and view the equation as a quadratic in $a$ : $a^2 - (3bc) a + (b^2 + c^2) = 0$ . Vieta: the two roots sum to $3bc$ and multiply to $b^2 + c^2$ . Given one root $a$ , the other is $a' = 3bc - a = (b^2 + c^2)/a$ .

If $a$ is the largest of $\{a, b, c\}$ , then $a' < a$ . (Check: $a^2 \ge a$ times each of $b, c$ , so $a' = 3bc - a \le 3a - a < a$ when $b, c < a$ .) Iterating, we descend to a triple where the largest entry is at most as big as the others — necessarily $(1, 1, 1)$ .

This is the Markov triple tree, generated by the action of $\text{PGL}_2(\mathbb{Z})$ via Vieta jumps. The number of Markov triples below a bound $N$ is asymptotically $C (\log N)^2$ (Zagier 1982).

The same Vieta-jumping skeleton applies to:

Markov triples: as above, $a^2 + b^2 + c^2 = 3abc$ .
Pell-like equations: $x^2 - D y^2 = \pm 1$ admits a jumping descent if you treat one variable as fixed.
USAMO 1995 Problem 5 (related descent).
IMO 2003 Problem 6 (more elaborate; Vieta-jumping combined with bound chasing).
Tournament problems asking about rational-distance configurations with quadratic constraints.

Common Mistakes

Watch Out

Forgetting to verify the jumped value is positive

The jumped root $a' = kb - a$ might be zero or negative. The proof must rule these out before claiming a smaller counterexample. In IMO 1988, ruling out $a' = 0$ uses the non-perfect-square assumption; ruling out $a' < 0$ requires an inequality argument.

Watch Out

Forgetting to verify the jumped value is strictly smaller

$a' = a$ is a fixed point; iterating won't descend. Fixed points typically correspond to the base case of the problem (the smallest solution). The proof must show $a' < a$ to descend.

Watch Out

Assuming Vieta jumping always lands in the same set

The jumped pair $(a', b)$ should still satisfy the original relation — verify this is automatic from Vieta's formulas. Sometimes the problem has additional constraints (positivity, coprimality, etc.) and the jump must preserve those. Failure to preserve the constraints means the jump is invalid.

Watch Out

Confusing Vieta jumping with infinite descent

The two are siblings, not the same. Infinite descent constructs a strictly decreasing sequence of natural numbers, which is impossible. Vieta jumping is one specific way to get the descent: you use Vieta's formulas on a quadratic to find the smaller witness. Other descent techniques include $2$ -adic valuation arguments (Fermat's $4n+3$ proof of no sum of two squares).

Exercises

ExerciseCore

Problem

Show that if $(a, b)$ is a positive-integer solution to $a^2 + b^2 = 5ab + 1$ , then there is a strictly smaller positive-integer solution.

ExerciseAdvanced

Problem

Use Vieta jumping to show that the equation $x^2 + y^2 + 1 = xyz$ has positive-integer solutions $(x, y, z)$ only with $z = 3$ .

Cross-Network Links

ProofsPath: proof-by-infinite-descent is the parent technique; well-ordering-principle underwrites the descent argument; pigeonhole-principle-elementary is the dual "no-descent" companion.
TheoremPath: number-theory-and-ml treats the modular arithmetic prerequisites.
AlgebraPath: groups-foundations underwrites the Markov-triple group action.

References

See structured references block. Primary entry points: Engel "Problem-Solving Strategies" Ch 6 for the technique treatment; Andreescu-Enescu-Dospinescu "Mathematical Olympiad Treasures" for additional worked examples; Chen "Modern Olympiad Number Theory" (online) for a contemporary olympiad treatment.