# Vieta Root Jumping

This week, we learn about Vieta Root Jumping, a descent method which uses Vieta's formula to find additional solutions.

You should first read up on Vieta’s Formula.

How would you use Vieta Root Jumping to solve the following?

1. [IMO 2007/5] Let $a$ and $b$ be positive integers. Show that if $4ab-1 \mid (4a^2-1)^2$, then $a=b$.

2. Share a problem which uses the Vieta root jumping technique.

Note by Calvin Lin
6 years, 9 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:

Essentially, Mysterious 100 Degree Monic Polynomial shows we can even Vieta Jump for polynomials.

Another Exercise: Assume that $m$ and $n$ are odd integers such that

$m^{2} - n^{2} + 1 \mid n^{2} - 1$.

Prove that $m^{2} - n^{2} + 1$ is a perfect square.

Yet Another Exercise: Determine all pairs of positive integers $(a,b)$ such that

$\dfrac{a^2}{2ab^2-b^3+1}$

is a positive integer.

- 6 years, 9 months ago

Indeed. This post only begins to scratch the surface of ideas like this, which in itself is a special case of Fermat's method of Infinite Descent.

The Markov Spectrum, in which we approximate real numbers with rationals, is a non-trivial application of VTJ.

VTJ can also be applied to equations in 3 variables, like $x^2 + y^2 + z^2 = 3xyz+2$.

Staff - 6 years, 9 months ago

This one is one of my favorites!

Start out with noting that because $gcd(b, 4ab-1)=1$, we have: $4ab-1|(4a^2-1)^2$ $\iff 4ab-1|b^2(4a^2-1)^2$ $\implies 4ab-1 | 16a^4b^2-8a^2b^2+b^2$ $\implies 4ab-1 | (16a^2b^2)(a^2)-(4ab)(2ab)+b^2$ $\implies 4ab-1 | (1)(a^2)-(1)(2ab)+b^2$ $\implies 4ab-1|(a-b)^2$ The last step follows from $16a^2b^2\equiv (4ab)^2\equiv 1\pmod{4ab-1}$ and $4ab\equiv 1\pmod{4ab-1}$.

Let $(a,b)=(a_1, b_1)$ be a solution to $4ab-1|(a-b)^2$ with $a_1>b_1$ contradicting $a=b$ where $a_1$ and $b_1$ are both positive integers. Assume $a_1+b_1$ has the smallest sum among all pairs $(a,b)$ with $a>b$ , and I will prove this is absurd. To do so, I prove that there exists another solution $(a,b)=(a_2, b_1)$ with a smaller sum. Set $k=\frac{(a-b_1)^2}{4ab_1-1}$ be an equation in $a$. Expanding this we arrive at $4ab_1k-k=a^2-2ab_1+b_1^2$ $\implies a^2-a(2b_1+4b_1k)+b_1^2+k = 0$ This equation has roots $a=a_1, a_2$ so we can now use Vieta’s on the equation to attempt to prove that $a_1>a_2$. First, we must prove $a_2$ is a positive integer. Notice that from $a_1+a_2=2b_1+4b_1k$ via Vieta’s hence $a_2$ is an integer. Assume that $a_2$ is negative or zero. If $a_2$ is zero or negative, then we would have $a_1^2-a_1(2b_1+4b_1k)+b_1^2+k=0 \ge b^2+k$ absurd. Therefore, $a_2$ is a positive integer and $(a_2, b_1)$ is another pair that contradicts $a=b$. Now, $a_1a_2=b_1^2+k$ from Vieta's. Therefore, $a_2=\frac{b^2+k}{a_1}$. We desire to show that $a_2. $a_2< a_1$ $\iff \frac{b_1^2+k}{a_1} $\iff b_1^2+\frac{(a_1-b_1)^2}{4a_1b_1-1} $\iff \frac{(a_1-b_1)^2}{4a_1b_1-1} < (a_1-b_1)(a_1+b_1)$ [ \iff \frac{(a1-b1)}{4a1b1-1} < a1+b1 ] Notice that we can cancel $a_1-b_1$ from both sides because we assumed that $a_1>b_1$. The last inequality is true because $4a_1b_1-1>1$ henceforth we have arrived at the contradiction that $a_1+b_1>a_2+b_1$. Henceforth, it is impossible to have $a>b$ (our original assumption) and by similar logic it is impossible to have $b>a$ forcing $a=b$ $\Box$

- 6 years, 9 months ago

We want to force out a nice factorisation from $4ab - 1 \mid (4a^2-1)^2$. A few hit and trials lead me to consider:

$b^2(4a^2-1)^2 - (4ab-1)(4a^3b - 2ab + a^2) = (a-b)^2$.

So now, assume that there indeed exists distinct $(a,b)$ that satisfy $4ab-1 \mid (a-b)^2$.

Lemma: Suppose $(a,b)$ is a distinct positive integer solution to $\frac{(a-b)^2}{4ab-1} = k$ where WLOG $a > b$. Then $(b, \frac{b^2+k}{a})$ is also a solution.

Proof: Remark first that $(a-b)^{2}=(4ab-1)k ⇔a^{2}-(2b+4kb)a+b^{2}+k=0$. By Vieta's Formula for Roots, $\frac{b^2+k}{a} = 2b + 4kb \in \mathbb{Z^{+}}$ whence $(b, \frac{b^2+k}{a} )$ is also a solution. □

However, we easily see that $\frac{b^2+k}{a} = b(2+4k) > b$ since by assumption $k$ is positive. This means that given a solution $(a,b)$ where $b$ is taken to be minimum, we can always vieta jump to a smaller solution, a clear contradiction. ■

- 6 years, 9 months ago

Problem: Show that if $x, y, z$ are positive integers, then $(xy+1)(yz+1)(zx+1)$ is a perfect square if and only if $xy+1, yz+1, zx+1$ are all perfect squares.

- 6 years, 9 months ago

So, here's my proposed solution.

Solution: It is trivial how to prove the 'if' part. Let us proceed to prove the 'only if' part. Suppose $x,y,z$ are such integers with $xy+1, yz+1, zx+1$ not all squares. Let us also assume that $x,y,z$ is the smallest counterexample, that is, $x+y+z$ is minimum.

WLOG, $xy+1$ is not a perfect square. As Dinesh Chavan wrote below, let $s$ be the smallest positive root of $s^2+x^2+y^2+z^2-2(xy+yz+zs+sx+zx+sy)-4xyzs-4 = 0$. This can be, as he said, written equivalently as:

$\\ (x+y-z-s)^2 = 4(xy+1)(zs+1),\\ (x+z-y-s)^2 = 4(xz+1)(ys+1),\\ (x+s-y-z)^2 = 4(xs+1)(yz+1).$

But then, our quadratic formula has root $s = x+y+z+2xyz\pm 2\sqrt{(xy+1)(yz+1)(zx+1)}$ which was given to be an integer, so we have that RHS is a square. This implies that $(xs+1)(ys+1)(zs+1)$ is a square.

Since, $xs+1\ge0,ys+1\ge0,zs+1\ge0$, we have that by verifying that $x=y=z=1$ is not a solution, $s\ge-\frac{1}{\max(x,y,z)}>-1$.

If $s = 0$, by crunching out the algebra one gets that $(x+y-z)^2 = 4(xy+1)$ which implies that $xy+1$ is a square, a clear contradiction.

So we have $s > 0$ and by the assumed minimality of $x+y+z$ we can safely conclude that $s≥ z$. Let the $2$ roots be $s, s_1$. By Vieta, we have:

$ss_1 = x^2+y^2+z^2-2xy-2yz-2zx-4 < z^2-x(2z-x)-y(2z-y) < z^2$

Now I hope that Ram Sharma sees the connection to Vieta Jumping.

- 6 years, 9 months ago

@Anqi Li Can you add this to the Vieta Root Jumping Wiki? Thanks!

Staff - 5 years, 11 months ago

Hi, this is a nice question. First We state a lemma

Lemma: If $(x,y,z)$ is a $P$ set, then so is $(x,y,z,s)$ for $s=x+y+z+2xyz \pm2\sqrt{(xy+1)(yz+1)(xz+1)}$ as long as s is positive.

Proof: Note that the value of s mentioned is the root of the equation $x^2+y^2+z^2+s^2-2(xy+yz+zx+xs+ys+zs)-4xyzs-4=0$ and now the above quadratic can be written as follows;

$(x+y-z-s)^2=4(xy+1)(zs+1)$ Also it can be written as; $(x+z-y-s)^2=4(xz+1)(ys+1)$ which can again be written as $(x+s-y-z)^2=4(xs+1)(yz+1)$ Since, $xy+1$ is an integer which is the quotient of two perfect squares, it is also a square. Similarly we can show for $yz+1$ and $zx+1$. Which shows that they all must be perfect squares.

- 6 years, 9 months ago

I don't know what the above question has to do with Vieta Root Jumping. However very well explained.+1 for the solution.Is there any other method to prove the result.

- 6 years, 9 months ago

Can you define your terms? What is a P set? Does it use 3 variables or 4 variables?

How is $xy+1$ a quotient of 2 perfect squares? Is $zs+1$ a perfect square? If so, why?

Staff - 6 years, 9 months ago