Vieta jumping

http://www.dreamstime.com/stock-images-three-happy-children-jumping-once-image8414304

I recently came across the method of Vieta jumping for proofs in number theory. In the first place, it sounds cute; in the second place, it’s a neat way to tackle some problems which without it look impossible. It’s like a sort of super-charged proof-by-induction where ordinary proof-by-induction is not strong enough.

It’s also an example of an important strand in mathematical problem-solving, where you make progress by cross-cutting between one area of maths and another and so re-framing the problem.

It’s not a dance or a sport, but a way of using the facts about sums and products of roots of quadratic equations. (Those facts are called Vieta equations, after the mathematician who first formulated them).

It goes like this. We prove claims which say such-and-such is true for all pairs of whole numbers by assuming a smallest pair for which such-and-such is not true, and getting a contradiction.

We switch from number theory into algebra. We turn the claim into a quadratic equation where we put a variable x in place of the first number in the pair, and the second appears as a “constant” in the coefficients. The first number in this pair is a root of the quadratic. Using the facts about sum and product of roots, we get a second root.

If we can show that this second root is a whole number, and that with the second number from the supposedly smallest pair it forms an even smaller pair, then we have a contradiction which proves our original claim.

Here’s an example with an interesting history. It’s the first problem for which Vieta jumping was developed as a method to solve it. It was set for the International Mathematical Olympiad (a competition for high school students) in 1988. The problem-setters were doubtful about including it because none of the professional mathematicians they tried it out on could solve it. Then eleven of the high school students competing in the Olympiad solved it.

For most whole numbers a and b ≥0, c=(a2+b2)/(ab+1) is not a whole number.

For a few pairs (a,b) (let’s assume we list them with the bigger number first, i.e. a≥b), it is. For example:

if b=0, then c=a2

if a=1 and b=1, then c=1

(82+22)/(8×2+1)=4

(272+32)/(27×3+1)=9

(302+82)/(30×8+1)=4

For any positive whole number n, if a=n5−n and b=n3, or a=n3 and b=n, then (a2+b2)/(ab+1)=n2.

All these whole-number answers are squares. Does the pattern continue? If (a2+b2)/(ab+1) is a whole number, is it always a square?

Yes. To prove this, take any whole number k which for some a and b = (a2+b2)/(ab+1)

We want to prove that k must be a square

There may be various different pairs (a,b) with a≥b for which k=(a2+b2)/(ab+1). Take the pair (α,β) for which α+β is smallest. If the claim that k must be a square is correct, then this pair will be (√k,0).

If β=0, then k=α2 and we’re done. What happens if α≥β>0 and k isn’t a square? We’ll find we get a contradiction. That proves k must in fact be a square.

Look at the equation (x22)/(xβ+1) = k, or, rearranged:

x2−kβx+β2−k=0

x=α is a root of this equation. Let x=ξ be the other root

Since the sum of the roots is kβ

ξ=kβ−α (and so ξ is a whole number)

Since the product of the roots is β2−k

ξ=(β2−k)/α (and so ξ can’t be 0, or else k would be a square, namely β2)

Also ξ<β2/α; so ξ<α, and ξ+β<α+β

We have a contradiction.

α+β is supposed to be the smallest pair (a,b) for which k=(a2+b2)/(ab+1), but now we have a pair β+ξ which is smaller

Or, at least, we have a contradiction so long as we can also prove that ξ≥0

If ξ<0 then ξ≤−1 (since ξ is a whole number), and:

0 = ξ2−kβξ+β2−k > ξ2+k+β2−k > 0, which is impossible

Therefore we do have a contradiction. Therefore k must in fact be a square. ▇

Reading a=1 to 64 across, and b=1 to 64 down, this chart shows the values of a and b ≤ 64 (other than a or b = 0) for which (a2+b2)/(ab+1) is a whole number.

grid

Want to practise Vieta jumping? Try this:

Suppose a, b and c are positive integers, such that 0<a2+b2+c2−abc<c. Show that a2+b2+c2−abc is a perfect square.

Solution here.