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 aa and bb be positive integers. Show that if 4ab1(4a21)2 4ab-1 \mid (4a^2-1)^2 , then a=ba=b .

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

Note by Calvin Lin
5 years, 10 months ago

No vote yet
14 votes

  Easy Math Editor

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.
  • Stay on topic — we're all here to learn more about math and science, not to hear about your favorite get-rich-quick scheme or current world events.

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 \( ... \) or \[ ... \] 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

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

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

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

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

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

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

is a positive integer.

Anqi Li - 5 years, 10 months ago

Log in to reply

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 x2+y2+z2=3xyz+2 x^2 + y^2 + z^2 = 3xyz+2 .

Calvin Lin Staff - 5 years, 10 months ago

Log in to reply

This one is one of my favorites!

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

Let (a,b)=(a1,b1)(a,b)=(a_1, b_1) be a solution to 4ab1(ab)24ab-1|(a-b)^2 with a1>b1a_1>b_1 contradicting a=ba=b where a1a_1 and b1b_1 are both positive integers. Assume a1+b1a_1+b_1 has the smallest sum among all pairs (a,b)(a,b) with a>ba>b , and I will prove this is absurd. To do so, I prove that there exists another solution (a,b)=(a2,b1)(a,b)=(a_2, b_1) with a smaller sum. Set k=(ab1)24ab11k=\frac{(a-b_1)^2}{4ab_1-1} be an equation in aa. Expanding this we arrive at 4ab1kk=a22ab1+b12 4ab_1k-k=a^2-2ab_1+b_1^2     a2a(2b1+4b1k)+b12+k=0 \implies a^2-a(2b_1+4b_1k)+b_1^2+k = 0 This equation has roots a=a1,a2a=a_1, a_2 so we can now use Vieta’s on the equation to attempt to prove that a1>a2a_1>a_2. First, we must prove a2a_2 is a positive integer. Notice that from a1+a2=2b1+4b1ka_1+a_2=2b_1+4b_1k via Vieta’s hence a2a_2 is an integer. Assume that a2a_2 is negative or zero. If a2a_2 is zero or negative, then we would have a12a1(2b1+4b1k)+b12+k=0b2+k a_1^2-a_1(2b_1+4b_1k)+b_1^2+k=0 \ge b^2+k absurd. Therefore, a2a_2 is a positive integer and (a2,b1)(a_2, b_1) is another pair that contradicts a=ba=b. Now, a1a2=b12+ka_1a_2=b_1^2+k from Vieta's. Therefore, a2=b2+ka1a_2=\frac{b^2+k}{a_1}. We desire to show that a2<a1a_2<a_1. a2<a1a_2< a_1     b12+ka1<a1\iff \frac{b_1^2+k}{a_1}<a_1     b12+(a1b1)24a1b11<a12 \iff b_1^2+\frac{(a_1-b_1)^2}{4a_1b_1-1}<a_1^2     (a1b1)24a1b11<(a1b1)(a1+b1) \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 a1b1a_1-b_1 from both sides because we assumed that a1>b1a_1>b_1. The last inequality is true because 4a1b11>14a_1b_1-1>1 henceforth we have arrived at the contradiction that a1+b1>a2+b1a_1+b_1>a_2+b_1. Henceforth, it is impossible to have a>ba>b (our original assumption) and by similar logic it is impossible to have b>ab>a forcing a=ba=b \Box

Justin Stevens - 5 years, 10 months ago

Log in to reply

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

b2(4a21)2(4ab1)(4a3b2ab+a2)=(ab)2 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) (a,b) that satisfy 4ab1(ab)2 4ab-1 \mid (a-b)^2 .

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

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

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

Anqi Li - 5 years, 10 months ago

Log in to reply

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

Anqi Li - 5 years, 10 months ago

Log in to reply

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 x,y,z are such integers with xy+1,yz+1,zx+1 xy+1, yz+1, zx+1 not all squares. Let us also assume that x,y,z x,y,z is the smallest counterexample, that is, x+y+z x+y+z is minimum.

WLOG, xy+1 xy+1 is not a perfect square. As Dinesh Chavan wrote below, let s s be the smallest positive root of s2+x2+y2+z22(xy+yz+zs+sx+zx+sy)4xyzs4=0 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+yzs)2=4(xy+1)(zs+1),(x+zys)2=4(xz+1)(ys+1),(x+syz)2=4(xs+1)(yz+1). \\ (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±2(xy+1)(yz+1)(zx+1) 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) (xs+1)(ys+1)(zs+1) is a square.

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

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

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

ss1=x2+y2+z22xy2yz2zx4<z2x(2zx)y(2zy)<z2 ss_1 = x^2+y^2+z^2-2xy-2yz-2zx-4 < z^2-x(2z-x)-y(2z-y) < z^2

a clear contradiction. ■

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

Anqi Li - 5 years, 10 months ago

Log in to reply

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

Calvin Lin Staff - 4 years, 11 months ago

Log in to reply

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

Lemma: If (x,y,z)(x,y,z) is a PP set, then so is (x,y,z,s)(x,y,z,s) for s=x+y+z+2xyz±2(xy+1)(yz+1)(xz+1)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 x2+y2+z2+s22(xy+yz+zx+xs+ys+zs)4xyzs4=0x^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+yzs)2=4(xy+1)(zs+1)(x+y-z-s)^2=4(xy+1)(zs+1) Also it can be written as; (x+zys)2=4(xz+1)(ys+1)(x+z-y-s)^2=4(xz+1)(ys+1) which can again be written as (x+syz)2=4(xs+1)(yz+1)(x+s-y-z)^2=4(xs+1)(yz+1) Since, xy+1xy+1 is an integer which is the quotient of two perfect squares, it is also a square. Similarly we can show for yz+1yz+1 and zx+1zx+1. Which shows that they all must be perfect squares.

Dinesh Chavan - 5 years, 10 months ago

Log in to reply

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.

Ram sharma - 5 years, 10 months ago

Log in to reply

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

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

Calvin Lin Staff - 5 years, 10 months ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...