×

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
3 years, 11 months ago

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:

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_1$$. $a_2< a_1$ $\iff \frac{b_1^2+k}{a_1}<a_1$ $\iff b_1^2+\frac{(a_1-b_1)^2}{4a_1b_1-1}<a_1^2$ $\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$$

- 3 years, 11 months ago

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.

- 3 years, 11 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 - 3 years, 11 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.

- 3 years, 11 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.

- 3 years, 11 months ago

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

Staff - 3 years 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.

- 3 years, 11 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 - 3 years, 11 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.

- 3 years, 11 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. ■

- 3 years, 11 months ago