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 aa and bb be positive integers such that ab+1ab + 1 divides a2+b2.a^2 + b^2. Show that a2+b2ab+1\frac{a^2 + b^2}{ab + 1} is a perfect square.

Solution: Main Idea: suppose a2+b2ab+1=k.\frac{a^2 + b^2}{ab + 1}=k. Then for a fixed k,k, the set of solutions has a very interesting structure, described by the following lemma.

Lemma. Suppose (a,b)(a,b) is a positive integer solution of the equation a2+b2ab+1=k.\frac{a^2 + b^2}{ab + 1}=k. Then (b,b2ka)(b,\frac{b^2-k}{a}) also is a solution.

Proof: Consider the quadratic equation x2kbx+(b2k)=0.x^2-kb\cdot x + (b^2-k)=0. For a given solution (a,b) (a,b) , we know that aa is a root of the above equation. By Vieta (sum of roots), we know that the other root is kba kb-a , which is an integer. Using the product of roots, the other root can be written as b2ka \frac{b^2-k}{a} . _\square

If ab,a \geq b, let the other root be c=b2kac=\frac{b^2-k}{a}. We have c<b2ab. c < \frac {b^2} {a} \leq b. If c<0,c<0, then c2kbc+(b2k)c2+k+b2k>0,c^2-kbc+(b^2-k)\geq c^2+k+b^2-k>0, which contradicts cc being the root of the equation. If c=0,c=0, then b2=k,b^2=k, so kk is a perfect square and we are done. Otherwise, we can keep going, using (b,c)(b,c) instead of (a,b)(a,b). We get a decreasing sequence of positive integers {a1,a2,a3,...}={a,b,b2ka,...}\{a_1,a_2,a_3,...\}=\{a,b,\frac{b^2-k}{a},...\} so that for all nn the pair(an,an+1)(a_n,a_{n+1}) satisfies an2+an+12anan+1+1=k.\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,0, proving that kk is a perfect square. _\square

The infinite sequence {an}\{a_n\} as above is what distinguishes Vieta Jumping from other descent methods. Note that each consecutive pair is a solution, and ana_n and an+2a_{n+2} are two roots of a quadratic equation that involves an+1a_{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,a, b,b, and cc are positive integers, such that 0<a2+b2abc<c. 0 < a^2 + b^2 - abc < c. Show that a2+b2abca^2 + b^2 - abc is a perfect square.

Solution. Suppose a2+b2abc=d.a^2 + b^2 - abc=d. For fixed cc and dd consider all positive integer pairs (a.b)(a.b) such that a2+b2abc=d. a^2 + b^2 - abc=d. Then this set has recursive structure, given by the following lemma.

Lemma. Suppose (a,b)(a,b) satisfies the equation a2+b2abc=da^2+b^2-abc=d and b2db^2\neq d. Then (b,b2da)(b, \frac{b^2-d}{a}) also satisfies the equation (where bb is plugged in for aa and b2da \frac{b^2-d}{a} is plugged in for bb).

Proof of Lemma. The equation x2bcx+(b2d)x^2-bcx+(b^2-d) has aa as one of its roots. Because b2d0,b^2-d\neq 0, aa cannot be 0,0, and, by Vieta's formula, the other root is b2da.\frac{b^2-d}{a}.

Now suppose dd is not a perfect square. Staring from (a,b)(a,b) with a>b,a>b, we will apply the Lemma. Note that e=b2dae=\frac{b^2-d}{a} cannot be negative, otherwise we get a contradiction: 0=e2bce+b2d>e2+b2+c(be1)00=e^2-bce+b^2-d> e^2+b^2+c(-be-1)\geq 0 Since dd is not a perfect square, b2db^2-d cannot be 0,0, so e>0.e>0. Also, e<b2ab.e<\frac{b^2}{a} \leq b. We can continue and get an infinite decreasing sequence a,b,e...a,b,e... This is impossible, so dd must be a perfect square.

 

2. Find the number of pairs of non-negative integers (n,m)(n,m), such that 1n<m1001\leq n< m\leq 100, nm21n \mid m^2-1 and mn21m \mid n^2-1.

Solution: We will first prove the following lemma.

Lemma. Suppose pair (n,m)(n,m) is such that 1<n<m1<n<m, nm21n \mid m^2-1 and mn21m \mid n^2-1. Then the pair (k,n)=(n21m,n)(k,n) = (\frac{n^2-1}{m}, n) satisfies the conditions 1k<n1\leq k<n, kn21k \mid n^2-1 and nk21n \mid k^2-1.

Proof. The first two conditions are obvious. To prove the third one, note that m21(modn)m^2\equiv 1 \pmod{n} and mk1(modn)mk\equiv -1 \pmod{n}, thus k21(modn)k^2\equiv 1 \pmod{n} .

Now starting from any pair (n,m)(n,m) satisfying the condition above, we apply Lemma several times, producing smaller and smaller pairs, until we get to a pair (1,i)(1,i) for some i>1i>1. Note that the above construction can be uniquely reversed: the pair (n,m)(n,m) is obtained from a pair (k,n)(k,n) by setting m=n21km=\frac{n^2-1}{k}. So we can generate all pairs (n,m)(n,m) satisfying the conditions of the problem from pairs (1,i)(1,i) for 2i1002\leq i \leq 100. Specifically,

(1,2)(2,3)...(n,n+1)...(99,100)(1,2)\to (2,3)\to ...(n,n+1)\to ... (99,100)
(1,3)(3,8)(8,21)(21,55)(1,3)\to (3,8) \to (8,21) \to (21,55)
(1,4)(4,15)(12,56)(1,4)\to (4,15) \to (12,56)
(1,5)(5,24)(1,5) \to (5,24)
(1,6)(6,35)(1,6) \to (6, 35)
(1,7)(7,48)(1,7)\to (7,48)
(1,8)(8,63)(1,8) \to (8,63)
(1,9)(9,80)(1,9)\to (9,80)
(1,10)(10,99)(1,10)\to (10,99)
(1,11)(1,11)
......
(1,100)(1,100)

Overall, we get 9999 pairs with n=1n=1, plus 9898 pairs with m=n+1, n2m=n+1, \ n\geq 2, plus 1111 other pairs, for a grand total of 208208 pairs.

Note by Calvin Lin
5 years, 4 months ago

No vote yet
1 vote

</code>...<code></code> ... <code>.">   Easy Math Editor

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold

- bulleted
- list

  • bulleted
  • list

1. numbered
2. 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 1

paragraph 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 </span>...<span></span> ... <span> or </span>...<span></span> ... <span> to ensure proper formatting.
2 \times 3 2×3 2 \times 3
2^{34} 234 2^{34}
a_{i-1} ai1 a_{i-1}
\frac{2}{3} 23 \frac{2}{3}
\sqrt{2} 2 \sqrt{2}
\sum_{i=1}^3 i=13 \sum_{i=1}^3
\sin \theta sinθ \sin \theta
\boxed{123} 123 \boxed{123}

Comments

Sort by:

Top Newest

Could this (i.e., #2) be adapted to find all pairs (m,n)(m,n) with 1n<m1 \le n < m such that m(n41)m \mid (n^4-1) and n(m41)n \mid (m^4-1)?

Kieren MacMillan - 5 years, 2 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 - 5 years, 2 months ago

Log in to reply

What about the [simple] existence of the pair (k,n)=(n21m,n)(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 1i1001 \le i \le 100 when we "regenerate" the pairs?

Kieren MacMillan - 5 years, 1 month ago

Log in to reply

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

mathh mathh - 4 years, 4 months ago

Log in to reply

Thanks! Updated it :)

Calvin Lin Staff - 4 years, 4 months ago

Log in to reply

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

Racchit Jain - 2 years, 11 months ago

Log in to reply

why is there no wiki page on this impotant topic

Samuel Adekunle - 1 year, 8 months ago

Log in to reply

vieta root jumping

Calvin Lin Staff - 1 year, 8 months ago

Log in to reply

It says no one has explained

Samuel Adekunle - 1 year, 8 months ago

Log in to reply

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

Calvin Lin Staff - 1 year, 8 months ago

Log in to reply

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

Samuel Adekunle - 1 year, 8 months ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...