The Legendary Question 6

I say it’s legendary – I hadn’t heard of it before stumbling across this Numberphile video:

That said, it’s a question with a good story behind it: it’s from the 1988 International Mathematics Olympiad (which immediately says “this is a hard question”); it was marked with two asterisks to say “this is especially hard”.

So hard, in fact, that Terry Tao – who would go on to earn a Fields Medal and general renown as an incredible mathematician and role model – “only” scored one point out of a possible seven. (He still got a gold medal. It was around the time of his 13th birthday. “Only.” Pah.)

Anyway, here’s the question:

Let $a$ and $b$ be positive integers such that $ab+1$ divides $a^2+b^2$.

Show that $\frac{a^2+b^2}{ab+1}$ is the square of an integer.

If you’d like to have a go at it, please do! Obviously, don’t get disheartened if you struggle. It’s a two-asterisk IMO question. After the break, I’ll take you through my solution (which relied on a big hint from the video). And in case you missed the implication, there are spoilers below the line.

---

My solution

Here’s how far I got on my own.

I know that $\frac{a^2+b^2}{ab+1}$ is a positive integer, so I can write down that $\frac{a^2+b^2}{ab+1}=k$ – and rearrange to make it $a^2+b^2=k(ab+1)$.

I think it looks nicer if it’s all on one side:

• $a^2-kab+b^2-k=0$

And I’m trying to show that $k$ has to be a square.

I tried many things here, not limited to falling down a rabbit hole of discriminants. However, the hint of “look for other solutions” was the key one.

That is, what I’ve got here is a quadratic in either $a$ or $b$. (I’ll pick $a$, but it doesn’t really matter.) And the thing about the roots of quadratics is, you know what they sum to – the roots of $x^2+Bx+C=0$ sum to $-B$.

So here, given $k$ and $b$, there are (typically) two possible values for $a$, and they sum to $kb$.

Put another way, if you know $a$, $b$ and $k$ are a solution, then so are $kb-a$, $b$ and $k$.

For example, if you spot that $(a,b,k)=(0,2,4)$ is a solution, you immediately know that $(8,2,4)$ is also a solution. Because it’s symmetrical in $a$ and $b$, $(2,8,4)$ must also work. Then you can apply the trick again to get $(30,8,4)$, and so on – you can generate an infinite series of possible values for $a$; let’s call it $a_i$. The sequence is different for each given value of $k$. (In general, $a=a_i$, $b=a_{i\pm 1}$ is a solution for the given value of $k$.)

That sequence comes from the recurrence relation $a_{i+2}-k{a}_{i+1}+a_i=0$ – and recurrence relations like this are simple enough to solve!

You solve the characteristic equation, ${\lambda }^2-k\lambda +1=0$, to get $\lambda =\frac{k\pm \sqrt{k^2-4}}{2}$, and write down the solution: $a_n=A{(k+\sqrt{k^2-4})}^n+B{(k-\sqrt{k^2-4})}^n$ (subsuming the half into the constants).

There’s a clever bit here, too.

Thinking about the binomial expansion of each of the pieces, the even terms will be nice integers, but the odd terms will contain some multiple of the square root. So, any integer solutions for $a_n$ will need to account for that. There are two options:

1. Make the square root vanish - in the positive integers, $k^2-4$ is a square only for $k=2$.
2. Cancel the square root with an astute selection of constants – if $B=A$, the square roots will simply disappear.

Case (1) can be shown not to work: going back to $a^2-kab+b^2-k=0$, if $k=2$ then we have ${(a-b)}^2=2$, which has no integer solution ¹.

In case (2), it’s clear that $a_0=0$. Going back to the original setup, if $a=0$, we have $\frac{b^2}{1}=k$, which can only work if $k$ is a square number!

And there you have it! $k$ has to be a square.

---

Analysis

I’m not sure how convincingly I’ve shown that this is the only way to account for the square roots – it might be better to say that $B=A+C$ in general and say:

• $a_n=A({(k+\sqrt{k^2-4})}^n+{(k-\sqrt{k^2-4})}^n)+C{(k-\sqrt{k^2-4})}^n$

The $A$ term has no square roots in it, but the $C$ one certainly does – unless $C=0$.

I’m curious to hear about different solutions! As always, if you’ve got something to add, drop me an email.

Footnotes:

1. splosh