# 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 \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, $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
7 years, 4 months ago

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

• Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
• Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
• Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold
- bulleted- list
• bulleted
• list
1. numbered2. list
1. numbered
2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example link
> This is a quote
This is a quote
    # I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in $$ ... $$ or $ ... $ to ensure proper formatting.
2 \times 3 $2 \times 3$
2^{34} $2^{34}$
a_{i-1} $a_{i-1}$
\frac{2}{3} $\frac{2}{3}$
\sqrt{2} $\sqrt{2}$
\sum_{i=1}^3 $\sum_{i=1}^3$
\sin \theta $\sin \theta$
\boxed{123} $\boxed{123}$

Sort by:

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)$?

- 7 years, 2 months ago

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

Staff - 7 years, 2 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?

- 7 years ago

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

- 6 years, 3 months ago

Thanks! Updated it :)

Staff - 6 years, 3 months ago

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

- 4 years, 11 months ago

why is there no wiki page on this impotant topic

- 3 years, 7 months ago

Staff - 3 years, 7 months ago

It says no one has explained

- 3 years, 7 months ago

Please check again. Someone vandalized the page and I've reverted the edit.

Staff - 3 years, 7 months ago

Thank's a lot. But who would vandalize the page like that

- 3 years, 7 months ago