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 (else would require a tremendous amount of work).

The method of Vieta jumping, also known as root flipping, can be very useful in problems involving divisibility of positive integers. The idea is to assume the existence of a solution for which the statement in question is wrong, and then to consider the given relation as a quadratic equation in one of the variables. Using Vieta’s formula, we can display a second solution to this equation. The next step is to show that the new solution is valid and smaller than the previous one. Then by the argument of infinite descent or by assuming the minimality of the first solution, we get a contradiction.

It is a relatively new proof technique in solving mathematical Olympiad problems, and the first appearance is at the 1988 International Mathematical Olympiad.

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.

Usually, the lemma will say something along the lines of "if \(a\) is a solution for some constraint, then \(b\) is also a solution for the same constraint." This constraint is usually given by fixing one or more of the variables.

In the case of a quadratic, we can consider one such as

\[a^{2}-abc+c^2+b^{2}=0,\]

which is a quadratic in terms of \(a\). We know the properties of quadratics, i.e. there are always two solutions. Hence, if we fix \(b,c\) and let \(a=x\), then we are left with

\[x^{2}-bcx+c^{2}+b^{2}=0.\]

And we can use Vieta's formula (hence the name) to get a relationship between the two solutions. One we already know is \(a\), and the other (call it \(d\)) gives us \(a+d=bc\) and \(ad=b^2+c^2\).

Upon showing this relationship, it is generally helpful to look for ways to constrain the values of \(d\), such as by letting a relationship between \(a\) and \(b\) dictate another relationship between \(b\) and \(d\) and seeing where that goes.

The end goal depends on the problem, but will usually result in you being able to restrict the values you need to search down to a few numbers, or in other cases show a contradiction if conditions (what the problem is asking to prove) aren't met.

The Vieta root jumping technique allows you to approach problems like this:

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 (dubbed "The Legend of Question #6"), because the technique of Vieta jumping was not widely used.

(IMO1988/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.

-----
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 \(\left(b,\frac{b^2-k}{a}\right)\) also is a solution.

Proof of lemma:

Consider the quadratic equation \[x^2-kb\cdot x + (b^2-k)=0.\] We get this equation by fixing \(b,k\) and replacing \(a\) with \(x\).

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,...\}=\left\{a,b,\frac{b^2-k}{a},\ldots\right\}\] 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."

Let \(a\) and \(b\) be positive integers such that \( ab \mid a^2 + b^2 + 1 \). Show that \( a^2 + b^2 + 1 = 3ab \).

---

We see that \( (1,1) \), \( (1,2) \) and \( (2,5) \) are solutions. This suggests that the solutions are related to each other by Vieta root jumping.

If \( a = b \), then we have \( a^2 \mid a^2 + a^2 + 1 \), and thus \( a=b=1 \). Otherwise, suppose that \( 1 \leq a < b \) is a solution. Let \( a^2 + b^2 + 1 = k ab \).

Consider the following quadratic equation \( x^2 - kx a + a^2 + 1 = 0. \) Then, we know that \( x = b \) would be a solution to this quadratic equation, and the other solution is \( x_2 = ka - b = \frac{ a^2 + 1 } { b } \). Since \( x_2 = ka -b \), it is an integer. Since \( x_2 = \frac{ a^2 + 1 } { b } < a \), we get a smaller solution \( (x_2, a ) \).

Hence, starting with any solution \( (a,b) \), we can always backtrack along it until \( 1 = a \). This gives us \( b \mid b^2 + 2 \), or that \( b \mid 2 \). Hence, \( b = 1 \) or 2.

The value of \(k \) stays the same throughout. We can calculate that if \( (a,b) = (1,1) \), we get \( k = 3 \), and if \( (a,b) = (1,2) \) we still get \( k = 3 \). Hence, we must always have \( k = 3 \), or that \( a^2 + b^2 + 1 = 3 ab \). \(_\square\)

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

---

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 \(\left(b, \frac{b^2-d}{a}\right)\) also satisfies the equation \(\big(\)where \(b\) is plugged in for \(a\) and \( \frac{b^2-d}{a}\) is plugged in for \(b\big).\)

Proof of lemma:
The equation \(x^2-bcx+(b^2-d)=0\) 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}.\) \(_\square\)

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,\ldots,\) which is impossible. Therefore, \(d\) must be a perfect square. \(_\square\)

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

---

We will first prove the following lemma:

Lemma:
Suppose the 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) = \left(\frac{n^2-1}{m}, n\right)\) satisfies the conditions \(1\leq k<n\), \(k \mid n^2-1\), and \(n \mid k^2-1\).

Proof of lemma:
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}\), and thus \(k^2\equiv 1 \pmod{n} \). \(_\square\)

Now starting from any pair \((n,m)\) satisfying the condition above, we apply the 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 (15,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. \(_\square\)

(IMO 2007/5)

Let \(a\) and \(b\) be positive integers such that \( 4ab -1 \mid ( 4a^2 - 1) ^2 \). Show that \( a = b \).

---

It is hard to see how to apply Vieta's formula directly, since there is no easy way to "jump" from solution \( (x,x) \) to \( (x+1, x+1 ) \). The question suggests that \( (a-b) \) would be an important quantity to consider.

Suppose that \( (a,b) \) satisfies the conditions with \( a \neq b \). Observe that \[ 4ab -1 \, \Big|\, b^2 \big( 4a^2 - 1\big)^2 - (4ab - 1 ) \big( 4a^3 b - 2ab + a^2 \big) = ( a - b) ^2 .\] Fix \( k = \frac{ (a-b)^2 } { 4ab - 1 } > 0 \). We want to consider all positive integer solutions \( (x,y) \) to \( k = \frac{ ( x-y) ^2 } { 4 xy -1 } \). Let \( (A,B) \) be the solution pair which minimizes the sum of both values. Since the equation is symmetric, we may assume that \( A > B \).

Consider the quadratic equation \[ x^2 - (2B + 4kB) x + B^2 + k =0. \] It has 2 roots, namely \( x_1 = A \) and \( x_2 = 2B + 4kB - A = \frac{ B^2 + k } { A} \). By the minimality of \(A + B \), we get that \( x_2 \geq A \), or that \( \frac { B^2 + k } { A } \geq A \). So \( \frac{ (A-B)^2 } { 4AB-1} = k \geq A^2 - B^2 \Rightarrow A -B \geq (4AB-1)(A+B) \geq A+B \) , which is a contradiction.

Hence, this shows that no solution of distinct integers is possible. \(_\square\)

If \(a\) and \(b\) are positive integers such that \( \frac{ a^2 + b^2 } { ab -1 } = k \) is an integer, then \( k = 5 \).

---

Lemma 1:
Suppose a certain pair of integers \((a,b)\) is a solution to the equation \(n = \frac{a^2+b^2}{ab-1}\). Then I say the pair \(\Big(b, \frac{b^2+n}{a}\Big)\) is also an integer solution.

Proof:
Consider the equation \(x^2 - nbx + (b^2+n) = 0\). By assumption, \(a\) is one of the roots. Therefore, by Vieta's formulas, the other root is \(\frac{b^2+n}{a}\). By substituting the formula for \(n\), this equals \(\frac{a^2+ab^3}{a(ab-1)}\). We already know that the numerator is divisible by \(ab-1\) (since \(n\) is an integer), and it's clearly also divisible by \(a\). Since \(\gcd(a,ab-1) = 1\), the numerator is also divisible by \(a(ab-1)\). Hence the new root is an integer. Hence, \(\Big(b, \frac{b^2+n}{a}\Big)\) is also an integer solution to the equation. \(_\square\)

Lemma 2:
If \(a > b \ge 3\), then \(\frac{b^2+n}{a} < b\).

Proof:
Since \(b \ge 3\), it follows that \(\frac{2b}{b^2-1} < 1\). Therefore, \[\begin{align} \frac{b^3+b}{b^2-1} = b + \frac{2b}{b^2-1} < b +1 &\le a\\\\ b^3+b &< ab^2-a\\\\ a+b^3 &< ab^2-b\\\\ \frac{a+b^3}{ab-1} &< b\\\\ \frac{b^2+n}{a} &< b. \end{align}\] Hence \(\frac{b^2+n}{a} < b\). \(_\square\)

Now, let \((a,b)\) be the solution to \(n = \frac{a^2+b^2}{ab-1}\) such that the value of \(b\) is minimized (but nonnegative). Then, by Lemmas 1 and 2, we must have \(0 \le b \le 2\), otherwise it is possible to get a smaller value of \(b\).

• If \(b = 0\), then \(n = -a^2 \le 0\).
• If \(b = 1\), then \(n = \frac{a^2+1}{a-1} = a+1 + \frac{2}{a-1}\). Then \(a = 0,2,3\) and therefore \(n = -1, 5,5\) respectively.
• If \(b = 2\), then we have \(n = \frac{a^2 + 4}{2a-1}\). Thus \(4n = \frac{4a^2+16}{2a-1} = 2a+1+\frac{17}{2a-1}\). Hence, \(2a-1\) is a factor of 17. Therefore \(a = 1, 9\), and therefore \(n = 5\).

Therefore, the maximum possible value of \(n\) in any of these cases is 5. \(_\square\)

Ariel Gershon

See this problem.

1) Find all pairs of integers \( m, n \) such that \( \frac{ m } { n } + \frac{ n}{m} \) is also an integer.

2) [Vietnam 2002] Find all positive integers \(n\) for which the equation \( (a + b + c + d)^2 = n^2 abcd \) has a solution in positive integers.
Hint: Focus on the smallest solution and compare it to another solution to get a bound on \(n\).

3) [Putnam 1933] Prove that for every real number \(N\), the equation

\[ a^2 + b^2 + c^2 + d^2 = abc + bcd + cda + dab \]

has a solution in which \(a, b, c, d \) are all integers greater than \(N\).

4) [Sam Vandervelde] Let \(a, b, c \) be positive integers such that \( abc + 1 \mid a^2 + b^2 + c^2 \). Then, \( \frac{ a^2 + b^2 + c^2 } { abc + 1 } \) can be written as the sum of 2 positive squares.

Note: This generalizes to 4 or more variables. However, Lagrange 4-square theorem tells us that the case of 5 or more variables doesn't produce a meaningful condition.

5) Determine all pairs of positive integers \( (a,b) \) such that \( \frac{a^2}{2ab^2-b^3+1} \) is a positive integer.

6) [Calvin Lin] Show that the only positive integer solutions to \( a \mid b^2 - b + 1 \) and \( b \mid a^2 - a + 1 \) is \( (1,1) \).
Hint: Proceed as per usual to construct the family of solutions, and show that they are all the same.