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".

## 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.

No vote yet

1 vote

×

Problem Loading...

Note Loading...

Set Loading...

Easy Math Editor

`*italics*`

or`_italics_`

italics`**bold**`

or`__bold__`

boldNote: you must add a full line of space before and after lists for them to show up correctlyparagraph 1

paragraph 2

`[example link](https://brilliant.org)`

`> This is a quote`

Remember to wrap math in \( ... \) or \[ ... \] to ensure proper formatting.`2 \times 3`

`2^{34}`

`a_{i-1}`

`\frac{2}{3}`

`\sqrt{2}`

`\sum_{i=1}^3`

`\sin \theta`

`\boxed{123}`

## Comments

Sort by:

TopNewestwhy is there no wiki page on this impotant topic

Log in to reply

vieta root jumping

Log in to reply

It says no one has explained

Log in to reply

Log in to reply

Log in to reply

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

Log in to reply

We have \(mk=n^2-1\), so \(mk\equiv -1\pmod {n}\), not \(mk\equiv 1\pmod {n}\).

Log in to reply

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?

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)\)?Log in to reply

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

Log in to reply