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.

## Comments

Sort by:

TopNewestin the IMO problem how does one number in the sequence becoming 0 proves that k is a perfect square? – Racchit Jain · 8 months, 3 weeks ago

Log in to reply

We have \(mk=n^2-1\), so \(mk\equiv -1\pmod {n}\), not \(mk\equiv 1\pmod {n}\). – Mathh Mathh · 2 years, 1 month ago

Log in to reply

– Calvin Lin Staff · 2 years, 1 month ago

Thanks! Updated it :)Log in to reply

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? – Kieren MacMillan · 2 years, 10 months ago

Log in to reply

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)\)? – Kieren MacMillan · 2 years, 12 months agoLog in to reply

– Calvin Lin Staff · 2 years, 12 months ago

It could. I believe that a similar Lemma holds. What happens when you try and work through the details?Log in to reply