I found about this legendary problem from a Numberphile video and was intrigued. Go watch the video, even if you have seen the problem before. It’s fun!
Here’s the problem which is can be found on The Official IMO page.
1988 IMO #6. Let $a$ and $b$ be positive integers such that $ab + 1$ divides $a^2 + b^2$.
Show that $\dfrac{a^{2} + b^{2}}{ab + 1}$ is the square of an integer.
I thought about the problem for some time and initially thought it was about Gaussian primes. But I got nowhere, so I wrote a simple Python program to collect some data. Denoting the ratio $\dfrac{a^{2} + b^{2}}{ab + 1}$ by $q$, here’s what I found (notice that I considered non-negative integers, rather than just strictly positive integers).:
$$\begin{array}{c||cccccccccc}
a & 1 & 1 & 2 & 3 & 8 & 27 & 30 & 112 & 240 & 418 \\ \hline
b & 0 & 1 & 0 & 0 & 2 & 3 & 8 & 30 & 27 & 112 \\ \hline
q & 1 & 1 & 4 & 9 & 4 & 9 & 4 & 4 & 9 & 4 \\
\end{array}$$
More thoughts…
What struck me about this data were the solutions for $q = 4$. They are adjacent terms in the sequence
$$0, 2, 8, 30, 112, 418, \dots$$
After some thought, I realized that this sequence satisfies the recurrence $T_n = 4 T_{n-1} – T_{n-2}$.
And the solutions for $q = 9$ are adjacent terms in the sequence $$0, 3, 27, 240, \dots$$
This sequence satisfies the recurrence $T_n = 9 T_{n-1} – T_{n-2}$.
Could it be, that for a fixed value of $q$, the integer solutions are adjacent terms of a 2nd order linear recurrence $T_n = q T_{n-1} – T_{n-2}$?!?
Given one solution $(a,b)$ with $a > b$, the recurrence yields the next solution, which is $(q a – b, a)$.
But the recurrence also determines the previous terms of the sequence: $T_{n-2} = q T_{n-1} – T_n$.
So the solution before $(a, b)$ would be $(b, q b – a)$. And if we keep generating smaller solutions, the process would have to bottom out somewhere, namely at $(T_1, T_0) = (r, 0)$ for some $r$.
Computing the ratio $q$ for this smallest solution yields that $q = r^2$, a perfect square, just as claimed in the problem!
With that intuition, here is what I proved:
Suppose that $a > b > 0$ are integers, and $\dfrac{a^2+b^2}{ab+1} = q$ is an integer. Define $a’ = b$ and $b’ = qb – a$. Then
1. The ratio $\dfrac{a’^2+b’^2}{a’b’+1}$ is also equal to $q$.
2. $q \geq 1$.
3. $a’ > b’$.
4. $b’ \geq 0$.
Thus, given a solution $(a,b)$, we can derive a smaller solution $(a’,b’)$. So the motivation described above is valid; any solution can be stepped down to a minimal solution $(r,0)$ whose $q$-value is the same as for $(a,b)$, and is $q = r^2$.
Proofs:
1. The ratio $\dfrac{a’^2+b’^2}{a’b’+1}$ is also equal to $q$.
Proof: Start by substitution and then use that $(a^2 + b^2) = q(ab+1)$.
$$\dfrac{a’^2+b’^2}{a’b’+1} = \dfrac{b^2+(qb – a)^2}{b(qb – a)+1} = \dfrac{q^2b^2 – 2qab + (a^2 + b^2)}{qb^2 – ab + 1} = \dfrac{q^2b^2 – 2qab + q(ab+1)}{qb^2 – ab + 1} = \dfrac{q^2b^2 – qab + q}{qb^2 – ab + 1} = q$$
2. $q \geq 1$. Proof: This is because $q$ is a positive integer!
3. $a’ > b’$. Proof: Start with $q = \dfrac{a^2+b^2}{ab+1}$ and decrease the denominator to get
$q < \dfrac{a^2+b^2}{ab} = \dfrac{a}{b} + \dfrac{b}{a} < \dfrac{a}{b} + 1$.
Then note that $q < \dfrac{a}{b} + 1$ is equivalent to $b > bq – a$ which is just $a’ > b’$.
4. $b’ \geq 0$.
Proof: In part 1 we saw that $\dfrac{b^2+(qb – a)^2}{b(qb – a)+1} = q$. We know that the numerator and the right hand side are positive. So the denominator must also be positive, which means that $b’ = qb-a \geq 0$.