Waste less time on Facebook — follow Brilliant.
×

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

No vote yet
14 votes

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

Comments

Sort by:

Top Newest

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

Justin Stevens - 3 years, 11 months ago

Log in to reply

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.

Anqi Li - 3 years, 11 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 \( x^2 + y^2 + z^2 = 3xyz+2 \).

Calvin Lin Staff - 3 years, 11 months ago

Log in to reply

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.

Anqi Li - 3 years, 11 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 \) 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 \)

a clear contradiction. ■

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

Anqi Li - 3 years, 11 months ago

Log in to reply

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

Calvin Lin Staff - 3 years ago

Log in to reply

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.

Dinesh Chavan - 3 years, 11 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 \) a quotient of 2 perfect squares? Is \( zs+1\) a perfect square? If so, why?

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

Log in to reply

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

Anqi Li - 3 years, 11 months ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...