×

# Vieta Root Jumping

Vieta Jumping is a nickname for a particular kind of descent method that has become quite popular in higher level math olympiad number theory problems. Like other instances of descent, it occurs when you have to solve a Diophantine equation (or system of equations, congruences or inequalities) whose solutions have some recursive structure. It is important to understand that Vieta Jumping is not a technique that you can choose to use or not to use: most Vieta Jumping problems can only be solved by Vieta Jumping.

How to recognize Vieta Jumping? Vieta Jumping is just a particular instance of a more general method of descent, so don't be surprised if the solutions in your problem have a more complicated recursive structure. The tell-tale sign of Vieta jumping is the existence of a Lemma (similar in spirit to the one below), which gives a relationship between different possible solutions. Look for a symmetric equation or congruence that has degree two in each of the two variables. (Note that there may also be other "parameter" variables in the problem.) Once such a lemma is recognized and established, you should look for some inequalities that will tell you in what direction to jump.

Perhaps the earliest Vieta Jumping problem was Problem 6 at the 1988 International Mathematical Olympiad. At the time, it was widely recognized as both beautiful and exceedingly hard, because the technique of Vieta Jumping was not widely used.

IMO'88/6. 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.

Solution: Main Idea: suppose $$\frac{a^2 + b^2}{ab + 1}=k.$$ Then for a fixed $$k,$$ the set of solutions has a very interesting structure, described by the following lemma.

Lemma. Suppose $$(a,b)$$ is a positive integer solution of the equation $$\frac{a^2 + b^2}{ab + 1}=k.$$ Then $$(b,\frac{b^2-k}{a})$$ also is a solution.

Proof: Consider the quadratic equation $x^2-kb\cdot x + (b^2-k)=0.$ For a given solution $$(a,b)$$, we know that $$a$$ is a root of the above equation. By Vieta (sum of roots), we know that the other root is $$kb-a$$, which is an integer. Using the product of roots, the other root can be written as $$\frac{b^2-k}{a}$$. $$_\square$$

If $$a \geq b,$$ let the other root be $$c=\frac{b^2-k}{a}$$. We have $$c < \frac {b^2} {a} \leq b.$$ If $$c<0,$$ then $$c^2-kbc+(b^2-k)\geq c^2+k+b^2-k>0,$$ which contradicts $$c$$ being the root of the equation. If $$c=0,$$ then $$b^2=k,$$ so $$k$$ is a perfect square and we are done. Otherwise, we can keep going, using $$(b,c)$$ instead of $$(a,b)$$. We get a decreasing sequence of positive integers $\{a_1,a_2,a_3,...\}=\{a,b,\frac{b^2-k}{a},...\}$ so that for all $$n$$ the pair$$(a_n,a_{n+1})$$ satisfies $$\frac{a_n^2+a_{n+1}^2}{a_na_{n+1}+1}=k.$$ Clearly, this sequence cannot continue indefinitely, so at some point one of the numbers will become $$0,$$ proving that $$k$$ is a perfect square. $$_\square$$

The infinite sequence $$\{a_n\}$$ as above is what distinguishes Vieta Jumping from other descent methods. Note that each consecutive pair is a solution, and $$a_n$$ and $$a_{n+2}$$ are two roots of a quadratic equation that involves $$a_{n+1}$$. The condition must be symmetric and the sequence must be in some sense decreasing, so the sequence must terminate. Note also that Vieta Jumping works both ways: one can recover all solutions from the terminal ones by "jumping back".

## Worked Examples

### 1. [Crux Mathematicorum] Suppose $$a,$$ $$b,$$ and $$c$$ are positive integers, such that $$0 < a^2 + b^2 - abc < c.$$ Show that $$a^2 + b^2 - abc$$ is a perfect square.

Solution. Suppose $$a^2 + b^2 - abc=d.$$ For fixed $$c$$ and $$d$$ consider all positive integer pairs $$(a.b)$$ such that $$a^2 + b^2 - abc=d.$$ Then this set has recursive structure, given by the following lemma.

Lemma. Suppose $$(a,b)$$ satisfies the equation $$a^2+b^2-abc=d$$ and $$b^2\neq d$$. Then $$(b, \frac{b^2-d}{a})$$ also satisfies the equation (where $$b$$ is plugged in for $$a$$ and $$\frac{b^2-d}{a}$$ is plugged in for $$b$$).

Proof of Lemma. The equation $$x^2-bcx+(b^2-d)$$ has $$a$$ as one of its roots. Because $$b^2-d\neq 0,$$ $$a$$ cannot be $$0,$$ and, by Vieta's formula, the other root is $$\frac{b^2-d}{a}.$$

Now suppose $$d$$ is not a perfect square. Staring from $$(a,b)$$ with $$a>b,$$ we will apply the Lemma. Note that $$e=\frac{b^2-d}{a}$$ cannot be negative, otherwise we get a contradiction: $0=e^2-bce+b^2-d> e^2+b^2+c(-be-1)\geq 0$ Since $$d$$ is not a perfect square, $$b^2-d$$ cannot be $$0,$$ so $$e>0.$$ Also, $$e<\frac{b^2}{a} \leq b.$$ We can continue and get an infinite decreasing sequence $$a,b,e...$$ This is impossible, so $$d$$ must be a perfect square.

### 2. Find the number of pairs of non-negative integers $$(n,m)$$, such that $$1\leq n< m\leq 100$$, $$n \mid m^2-1$$ and $$m \mid n^2-1$$.

Solution: We will first prove the following lemma.

Lemma. Suppose pair $$(n,m)$$ is such that $$1<n<m$$, $$n \mid m^2-1$$ and $$m \mid n^2-1$$. Then the pair $$(k,n) = (\frac{n^2-1}{m}, n)$$ satisfies the conditions $$1\leq k<n$$, $$k \mid n^2-1$$ and $$n \mid k^2-1$$.

Proof. The first two conditions are obvious. To prove the third one, note that $$m^2\equiv 1 \pmod{n}$$ and $$mk\equiv -1 \pmod{n}$$, thus $$k^2\equiv 1 \pmod{n}$$.

Now starting from any pair $$(n,m)$$ satisfying the condition above, we apply Lemma several times, producing smaller and smaller pairs, until we get to a pair $$(1,i)$$ for some $$i>1$$. Note that the above construction can be uniquely reversed: the pair $$(n,m)$$ is obtained from a pair $$(k,n)$$ by setting $$m=\frac{n^2-1}{k}$$. So we can generate all pairs $$(n,m)$$ satisfying the conditions of the problem from pairs $$(1,i)$$ for $$2\leq i \leq 100$$. Specifically,

$$(1,2)\to (2,3)\to ...(n,n+1)\to ... (99,100)$$
$$(1,3)\to (3,8) \to (8,21) \to (21,55)$$
$$(1,4)\to (4,15) \to (12,56)$$
$$(1,5) \to (5,24)$$
$$(1,6) \to (6, 35)$$
$$(1,7)\to (7,48)$$
$$(1,8) \to (8,63)$$
$$(1,9)\to (9,80)$$
$$(1,10)\to (10,99)$$
$$(1,11)$$
$$...$$
$$(1,100)$$

Overall, we get $$99$$ pairs with $$n=1$$, plus $$98$$ pairs with $$m=n+1, \ n\geq 2$$, plus $$11$$ other pairs, for a grand total of $$208$$ pairs.

Note by Calvin Lin
2 years, 9 months ago

Sort by:

in the IMO problem how does one number in the sequence becoming 0 proves that k is a perfect square? · 4 months, 2 weeks ago

We have $$mk=n^2-1$$, so $$mk\equiv -1\pmod {n}$$, not $$mk\equiv 1\pmod {n}$$. · 1 year, 9 months ago

Thanks! Updated it :) Staff · 1 year, 9 months ago

What about the [simple] existence of the pair $$(k,n)=(\tfrac{n^2-1}{m},n)$$ guarantees that we have found the complete set of solutions? Is it simply that we use all $$1 \le i \le 100$$ when we "regenerate" the pairs? · 2 years, 6 months ago

Could this (i.e., #2) be adapted to find all pairs $$(m,n)$$ with $$1 \le n < m$$ such that $$m \mid (n^4-1)$$ and $$n \mid (m^4-1)$$? · 2 years, 7 months ago