Overview

Vieta Jumping (also called root flipping) is an advanced technique for Diophantine equations. It applies when a rational expression in positive integers is asserted to equal an integer $k$, and the relation can be rearranged into a quadratic in one variable. The idea is that if $(a, b)$ is a solution, Vieta's formulas produce a second root $x$ that is also an integer, still paired with $b$, but strictly smaller than $a$. Since positive integers cannot decrease indefinitely, this forces either a contradiction or a checkable base case.

Key Idea

Suppose we have a relation involving positive integers $a, b$ and an integer $k$, which rearranges into a quadratic in $t$:

$t^2 - (kb)\,t + (b^2 - k) = 0$

The known value $a$ is one root. Let $x$ denote the other. Vieta's formulas give:

$x + a = kb \implies x = kb - a$ $x \cdot a = b^2 - k \implies x = \frac{b^2 - k}{a}$

The first expression proves $x \in \mathbb{Z}$ (since $k, a, b$ are all integers).

The second expression is used to bound $x$ and establish $x < a$, which produces the descent.

The two expressions give different information about the same quantity; combining them is what drives the argument.

Steps to Reproduce

Here is the standard structure of a Vieta Jumping argument:

1. Define $k$. Let $k = f(a,b)$ where $f$ is the expression asserted to be an integer (or a specific value).
2. Fix $k$, take the minimal pair. Among all pairs $(a, b)$ of positive integers with $f(a, b) = k$, choose the one minimizing $a + b$ (or just $a$ after WLOG $a \geq b$).
3. Form the quadratic. Rearrange the equation into a quadratic in $a$: the existing value $a$ is one root.
4. Produce the second root. Let $x$ be the other root. By Vieta's sum formula, $x = (\text{something}) - a \in \mathbb{Z}$.
5. Show $x > 0$. Use the product formula $xa = (\text{constant})$. If $k$ is not a perfect square or if the constant is positive, show $x \neq 0$; rule out $x < 0$ separately.
6. Show $x < a$. Use the assumption $a \geq b$ and the product formula: $x = \frac{b^2 - k}{a} \leq \frac{a^2 - k}{a} < a$.
7. Conclude. The pair $(x, b)$ satisfies the same relation with $x + b < a + b$, contradicting minimality. Hence no such pair exists (or $k$ must equal the forced value).

Worked Examples

Example 1 (IMO 1988 Problem 6). Let $a, b$ be positive integers such that $ab + 1 \mid a^2 + b^2$. Prove that $\dfrac{a^2 + b^2}{ab + 1}$ is a perfect square.

Proof. Let $k = \dfrac{a^2+b^2}{ab+1}$. We want to show $k$ is always a perfect square.

Suppose for contradiction that $k$ is a fixed positive integer that is not a perfect square, and that there exists at least one pair $(a,b)$ of non-negative integers with $\frac{a^2+b^2}{ab+1} = k$. Pick the pair $(a, b)$ with $a \geq b \geq 0$ that minimizes $a$.

Rewrite the equation as $a^2 + b^2 = k(ab + 1)$, then rearrange into a quadratic in $a$:

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

The value $a$ is one root. Let $x$ be the other root. By Vieta's formulas:

• Sum: $x + a = kb$, so $x = kb - a \in \mathbb{Z}$.
• Product: $x \cdot a = b^2 - k$, so $x = \dfrac{b^2 - k}{a}$.

Since $x$ is an integer satisfying the same quadratic, the pair $(x, b)$ satisfies $x^2 - kbx + (b^2 - k) = 0$, which means $x^2 + b^2 = k(xb + 1)$, i.e., $\frac{x^2 + b^2}{xb + 1} = k$ — so $(x, b)$ is also a valid solution, provided $x \geq 0$ and $xb + 1 > 0$.

$x \neq 0$: If $x = 0$, then $xa = b^2 - k = 0$, so $k = b^2$, contradicting our assumption that $k$ is not a perfect square.

$x \geq 0$: Suppose $x < 0$. Then $x^2 + b^2 = k(xb + 1)$. The left side is positive. We need $xb + 1 > 0$, i.e., $x > -1/b$ — but $x$ is a negative integer, so $x \leq -1$, giving $xb \leq -b \leq 0$, so $xb + 1 \leq 1$. Combined with $x^2 + b^2 > 0$, we need $xb + 1 > 0$, i.e., $xb \geq 0$. Since $x < 0$ and $b \geq 1$, this is impossible. So $x \geq 0$, and since $x \neq 0$, we have $x > 0$.

$x < a$: Since $a \geq b \geq 1$:

$x = \frac{b^2 - k}{a}$

We need to show this is less than $a$. Note $k \geq 1$, so $b^2 - k \leq b^2 - 1 < b^2 \leq a^2$, giving $x = \frac{b^2-k}{a} < \frac{a^2}{a} = a$.

But then $(x, b)$ is a valid pair achieving the same $k$, with $x < a$ — contradicting the minimality of $a$. Therefore, no non-perfect-square value of $k$ is achievable, and $k$ must be a perfect square. $\blacksquare$

Example 2. Let $a, b$ be positive integers with $ab \mid a^2 + b^2 + 1$. Show that $\dfrac{a^2 + b^2 + 1}{ab} = 3$.

Proof. Let $k = \frac{a^2+b^2+1}{ab}$. First handle the diagonal: if $a = b$, then $a^2 \mid 2a^2 + 1$, so $a^2 \mid 1$, forcing $a = b = 1$ and $k = 3$. Now assume $a > b \geq 1$ and pick the minimal-sum pair.

Rearrange as a quadratic in $a$:

$a^2 - kb\,a + (b^2 + 1) = 0$

The value $a$ is one root; let $x$ be the other. By Vieta's:

• Sum: $x = kb - a \in \mathbb{Z}$.
• Product: $xa = b^2 + 1 > 0$.

Since $xa = b^2 + 1 > 0$ and $a > 0$, we have $x > 0$.

$x < a$: Since $a > b$:

$x = \frac{b^2 + 1}{a} < \frac{b^2 + 1}{b} = b + \frac{1}{b} \leq b + 1 \leq a$

So $(x, b)$ is a valid pair with $x < a$, contradicting minimality — unless no such pair with $a > b$ exists. The descent terminates when $a = b$, which forces $k = 3$ as shown above. Therefore $k = 3$ for all valid pairs. $\blacksquare$

Common Pitfalls

Forgetting to prove $x > 0$. The extremal argument only produces a contradiction if the new solution is a valid pair of positive integers. Always prove $x > 0$, or handle $x = 0$ as an explicit base case.

Skipping $a = b$. The bound $x < a$ uses $a > b$. The equality case $a = b$ must always be checked first, this often forces the answer immediately.

Not verifying the new pair satisfies the relation. Check that $(x, b)$ (not just $(a, b)$) satisfies the original equation before claiming it's a valid smaller solution.

Negative variables. The extremal principle requires $a + b$ to be bounded below. If the problem allows negative integers, the descent has no floor. Establish that any solution can be transformed to a positive one before applying the method.

Practice Problems