Number TheoryDifficulty 80-10013 tagged problems

Vieta Jumping

Vieta Jumping is the habit of descending to a smaller solution by treating a Diophantine equation as a quadratic. In contest math, that habit turns a crowded setup into a relation the student can test, bound, count, or compute. MathGrit teaches it as a recognizable signal, a deliberate move, and a final translation back to the original question.

Practice this technique Match my level

The Key Result

If $a$ is an integer root of $a^2 - sa + p = 0$ with $s, p \in \mathbb{Z}$, the partner root $a' = s - a \in \mathbb{Z}$ — so any integer solution jumps to another, enabling descent.

If a symmetric Diophantine equation is quadratic in one variable, Vieta's formulas hand you a second integer root, letting you 'jump' to a smaller solution and run infinite descent.

Why It Works

1
Fix all variables but one, say $a$, so the equation becomes a quadratic $a^2 - (\text{sum})\,a + (\text{product}) = 0$ with the known root $a$.
2
By Vieta's formulas the two roots satisfy $a + a' = \text{sum}$ and $a\,a' = \text{product}$; since both the sum and product are integers and $a$ is an integer, the partner root $a' = \text{sum} - a$ is also an integer.
3
So $(a', b)$ is another integer solution. Choosing the original solution to minimize a positive quantity (like $a + b$) and showing $a'$ is smaller yet still valid produces a contradiction by descent.
4
Cornering the descent — usually $a'$ cannot stay positive and below the minimum, forcing a boundary case (e.g. $a' = 0$) — pins down all solutions or a hidden invariant.

Worked Examples

Example 1

Show that if $a, b$ are positive integers with $ab + 1 \mid a^2 + b^2$, then $k = \frac{a^2 + b^2}{ab + 1}$ is a perfect square. (IMO 1988, Problem 6 — sketch.)

1
Fix $k$ and suppose, for contradiction, $k$ is not a perfect square. Among all positive-integer solutions $(a,b)$ of $a^2 + b^2 = k(ab + 1)$, pick one minimizing $a + b$, and assume $a \ge b$ (WLOG).
2
View it as a quadratic in $a$: $a^2 - (kb)\,a + (b^2 - k) = 0$. The given $a$ is one root; let $a'$ be the other. By Vieta, $a + a' = kb$ and $a\,a' = b^2 - k$. From $a + a' = kb$, $a' = kb - a$ is an integer; equivalently $a' = \frac{b^2 - k}{a}$.
3
We first rule out $a' < 0$. Suppose $a' < 0$; since $a'$ is an integer, $a' \le -1$, and with $b \ge 1$ this gives $a'b \le -1$, so $a'b + 1 \le 0$. The second root satisfies the same quadratic, $a'^2 - kb\,a' + (b^2 - k) = 0$, which rearranges to $a'^2 + b^2 = k(a'b + 1)$. The right side is $k(a'b + 1) \le 0$ (as $k > 0$ and $a'b + 1 \le 0$), while the left side is $a'^2 + b^2 \ge b^2 > 0$ — a contradiction. Hence $a' \ge 0$.
4
If $a' = 0$, then $a\,a' = b^2 - k = 0$, so $k = b^2$ is a perfect square, contradicting the assumption. So $a' \ge 1$, a positive integer, and $(a', b)$ is again a valid positive-integer solution for the same $k$. Then $a' = \frac{b^2 - k}{a} \le \frac{b^2}{a} \le \frac{a^2}{a} = a$, and in fact $a' < a$ (since $k \ge 1$ forces $a' = \frac{b^2-k}{a} < \frac{a^2}{a} = a$), so $a' + b < a + b$ — a strictly smaller solution, contradicting minimality. Every branch is contradictory, so $k$ must be a perfect square.

Answer:

$k = \dfrac{a^2 + b^2}{ab + 1}$ is always a perfect square.

Warm-up

The equation $a^2 + b^2 + 1 = 3ab$ has the solution $(a, b) = (1, 1)$. Use Vieta jumping to generate the next two positive-integer solutions.

1
First verify $(1,1)$: $1 + 1 + 1 = 3 = 3 \cdot 1 \cdot 1$. ✓
2
Fix $b = 1$ and view the equation as a quadratic in $a$: $a^2 - 3a + 2 = 0$. One root is the known $a = 1$; by Vieta the roots sum to $3$, so the partner root is $a' = 3 - 1 = 2$. Thus $(2, 1)$ is a new solution: $4 + 1 + 1 = 6 = 3 \cdot 2 \cdot 1$. ✓
3
Now fix $a = 2$ and jump on $b$: $b^2 - 6b + 5 = 0$, with known root $b = 1$ and partner $b' = 6 - 1 = 5$. So $(2, 5)$ works: $4 + 25 + 1 = 30 = 3 \cdot 2 \cdot 5$. ✓
4
The jumps walk up a ladder $(1,1) \to (2,1) \to (2,5) \to (13,5) \to \cdots$ — exactly the odd-indexed Fibonacci pairs.

Answer:

Next solutions: $(2, 1)$ and $(2, 5)$.

Contest level

Let $a, b$ be positive integers such that $ab \mid a^2 + b^2 + 1$. Prove that $\frac{a^2 + b^2 + 1}{ab} = 3$.

1
Let $k = \frac{a^2 + b^2 + 1}{ab}$, a positive integer. Among all positive-integer pairs giving this same $k$, choose one with $a + b$ minimal, and assume $a \ge b$ (WLOG).
2
Fix $b$ and treat $a^2 - (kb)a + (b^2 + 1) = 0$ as a quadratic in $a$. The other root is $a' = kb - a$ (an integer) with $a a' = b^2 + 1 > 0$, so $a' > 0$ and $(a', b)$ is another valid solution for the same $k$.
3
By minimality $a' \ge a$. Then $a^2 \le a a' = b^2 + 1 \le a^2 + 1$, and since $a \ge b$ this squeezes $a = b$ (if $a > b$ then $b^2 + 1 \le (a-1)\cdot a < a^2$, contradiction unless $b = a$).
4
Set $a = b$ in the equation: $2a^2 + 1 = k a^2$, so $a^2(k - 2) = 1$, forcing $a = 1$ and $k - 2 = 1$, i.e. $k = 3$. (Base check: $(1,1)$ gives $\frac{3}{1} = 3$.) Hence the ratio is always $3$.

Answer:

$\frac{a^2 + b^2 + 1}{ab} = 3$.

Olympiad / Challenge

Find all positive integers $a, b$ for which $ab - 1 \mid a^2 + b^2$, and determine the value of $\frac{a^2 + b^2}{ab - 1}$.

1
Suppose $ab - 1 \mid a^2 + b^2$ with $ab > 1$, and let $k = \frac{a^2 + b^2}{ab - 1}$ be a fixed positive integer, so $a^2 + b^2 = k(ab - 1)$, i.e. $a^2 - (kb)\,a + (b^2 + k) = 0$. Among all positive-integer solutions of this equation for this $k$, choose one minimizing $a + b$, and label it so that $a \ge b \ge 1$.
2
Treat $a^2 - (kb)\,a + (b^2 + k) = 0$ as a quadratic in $a$ with the known integer root $a$. The second root is $a' = kb - a = \frac{b^2 + k}{a}$. The first form shows $a'$ is an integer; the second shows $a' > 0$ (as $b^2 + k > 0$), so $a'$ is a positive integer and $(a', b)$ is again a positive-integer solution with the same $k$.
3
Since $a + b$ was minimal over all solutions, $(a', b)$ cannot be smaller: $a' + b \ge a + b$, so $a' \ge a$. Equivalently $a\,a' = b^2 + k \ge a^2$, i.e. $k \ge a^2 - b^2$.
4
Now suppose for contradiction the minimal pair had $a > b \ge 2$. We compare $k$ with $a^2 - b^2$ directly: $(a^2 - b^2)(ab - 1) - (a^2 + b^2) = a\big(b(a-b)(a+b) - 2a\big)$, and since $a > b \ge 2$ we have $a - b \ge 1$ and $b \ge 2$, so $b(a-b)(a+b) \ge 2(a+b) > 2a$, making this positive. Hence $(a^2 - b^2)(ab - 1) > a^2 + b^2 = k(ab - 1)$, so $k < a^2 - b^2$ — contradicting $k \ge a^2 - b^2$ from the previous step. So the minimal pair cannot have $a > b \ge 2$.
5
The remaining possibilities for the minimal pair are $a = b$ or $b = 1$. If $a = b$ then $2a^2 = k(a^2 - 1)$, so $k = 2 + \frac{2}{a^2 - 1}$, which is an integer only if $(a^2 - 1) \mid 2$, i.e. $a^2 \in \{2, 3\}$ — impossible for an integer $a \ge 2$ (and $a = b = 1$ gives $ab - 1 = 0$). So the minimal pair has $b = 1$.
6
With $b = 1$ the equation is $a^2 + 1 = k(a - 1)$, so $(a - 1) \mid a^2 + 1 = (a - 1)(a + 1) + 2$, forcing $(a - 1) \mid 2$ and hence $a \in \{2, 3\}$. The base pairs are $(2, 1)$ and $(3, 1)$, giving $\frac{2^2 + 1}{2 \cdot 1 - 1} = 5$ and $\frac{3^2 + 1}{3 \cdot 1 - 1} = 5$. Every solution descends to one of these (and their reflections $(1,2),(1,3)$), so $k = 5$ for every solution.

Answer:

All solutions satisfy $\frac{a^2 + b^2}{ab - 1} = 5$ (e.g. $(1,2), (1,3), (2,1), (3,1)$ and their jumps).

Going Deeper

Generalization: Vieta jumping handles any equation symmetric (or made symmetric) and quadratic in a variable — $a^2 + b^2 = k(ab \pm 1)$, Markov's $x^2+y^2+z^2 = 3xyz$, and 'prove the ratio is constant / a perfect square' problems. The two roots $a + a' = (\text{linear coeff})$, $a a' = (\text{constant})$ are both forced to be integers, which is what lets you jump to a new lattice solution.
Where it appears: hard olympiad Diophantine/divisibility problems (the IMO 1988 #6 archetype), determining the constant value of a divisibility ratio, and generating infinite solution families (the jumps trace a 'Vieta tree' or Markov tree).
Pitfall: the descent MUST terminate at a genuine base case. Choose an extremal solution (minimize $a + b$ or $\max(a,b)$), prove the jumped root $a'$ is a positive integer and strictly smaller, and reach the contradiction or boundary — if $a'$ can be $0$ or negative you must handle that case explicitly (it often yields the answer, as $a' = 0$ did in IMO 1988). Forgetting to bound $a'$ below, or never reaching a base case, is the standard failed write-up.

Spot the Signal

Use it on symmetric Diophantine equations where a minimal solution can be pushed smaller.
You can describe the hard part as descending to a smaller solution by treating a Diophantine equation as a quadratic, but a direct attack starts producing clutter.
The problem rewards preserving structure instead of expanding, listing, or guessing too early.

Learn the Move

Start by fixing one variable, viewing the equation as a quadratic, and jumping to its other root.
Name the relation that makes Vieta Jumping legal before doing computation.
Use the new relation to replace the messiest part of the problem with a cleaner one.
Translate the result back to the quantity the problem actually asks for.

Avoid These Traps

Forgetting to argue minimality, or losing the integrality of the jumped root.
Applying Vieta Jumping because it sounds relevant, without checking the trigger first.
Stopping after spotting the technique instead of finishing the calculation or proof.

MathGrit Coach Note

Assume a minimal solution, then jump to a smaller one — and reach a contradiction.

Try it on:

Resolve an olympiad Diophantine equation by Vieta jumping.