Waste less time on Facebook — follow Brilliant.

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)\)

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
3 years, 6 months ago

No vote yet
1 vote


Sort by:

Top Newest

in the IMO problem how does one number in the sequence becoming 0 proves that k is a perfect square?

Racchit Jain - 1 year, 1 month 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, 6 months ago

Log in to reply

Thanks! Updated it :)

Calvin Lin Staff - 2 years, 6 months ago

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 - 3 years, 3 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 - 3 years, 4 months ago

Log in to reply

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

Calvin Lin Staff - 3 years, 4 months ago

Log in to reply


Problem Loading...

Note Loading...

Set Loading...