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.