An answer to the legendary “Question six”

Some simple algebra to answer one of the hardest questions in the history of the International Mathematical Olympiad

Note: this article makes use of MathML, the standard XML markup for math formulas. Sadly, this is not properly supported on some allegedly ‘modern’ and ‘feature-rich’ browsers. If the formulas don't make sense in your browser, consider reporting the issue to the respective developers and/or switching to a standard-compliant browser.

Introduction

You can find an introduction to the legendary “Question Six” in this Numberphile video. This article is my attempt at providing a “simple” answer to the problem, sketched from the hints provided in this more detailed insights video.

To be clear this isn't my personal “best effort” at trying to solve the problem (I did give it a quick try, starting from an intuition that induction would be the key, but I didn't get very far in). I also have no idea if this is how it was solved by any of the candidates that did provide the correct answer to the problem.

No, this is just a formalization into an actual proof of the hints provided by Simon Pampena in the second video. The proof should still be easy to follow even with only a basic knowledge of algebra.

The problem

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

$\frac{a^{2} + b^{2}}{a b + 1}$

is the square of an integer.

The solution

Let

$f (x, y) = \frac{x^{2} + y^{2}}{x y + 1} .$

We want to show that if $a, b$ are positive integers and $f (a, b)$ is an integer, then $f (a, b)$ is a square.

Observe first that if $a, b$ are non-negative integers, and one of them is 0, then the statement is trivially true, since $f (a, 0) = a^{2}$ and $f (0, b) = b^{2}$ .

Assume now that $a_{0}, b$ integers with $0 < a_{0} < b$ are such that $f (a_{0}, b)$ is an integer. We want to show that there exist a non-negative integer $a_{1} < a_{0}$ such that $f (a_{1}, a_{0}) = f (a_{0}, b)$ . Note that with this proven, we can apply the result iteratively, constructing a sequence ${a_{i}}$ with $0 \leq a_{i + 1} < a_{i}$ and such that $f (a_{i + i}, a_{i}) = f (a_{0}, b)$ . Given the strictly decreasing nature of the sequence and the non-negativity of the values, the sequence will terminate in $k < a_{0}$ steps, with $a_{k} = 0$ , leading to $f (a_{0}, b) = f (0, a_{k - 1}) = a_{k - 1}^{2}$ , proving that $f (a_{0}, b)$ is the square of an integer.

Let us then prove the existence of $a_{1}$ . Let $N = f (a_{0}, b)$ . By hypothesis, $N$ is an integer and we have

$\frac{a_{0}^{2} + b^{2}}{a_{0} b + 1} = N$

that with simple algebra can be rearranged into

$b^{2} - N a_{0} b + a_{0}^{2} - N = 0 . (⋆)$

This implies that the quadratic equation

$x^{2} - N a_{0} x + a_{0}^{2} - N = 0$

has the solution $x = b$ . Dividing the polynomial

$x^{2} - N a_{0} x + a_{0}^{2} - N$

by $x - b$ gives us1 the second root, $a_{1} = N a_{0} - b$ , which again is an integer.

We need to show that $a_{1} < a_{0}$ , i.e.

$N a_{0} - b < a_{0}$

or equivalently

$N a_{0} b - b^{2} < a_{0} b .$

Note that by bringing the leftmost two terms in the right-hand side of equation $(⋆)$ to the left-hand side and flipping the equation, we have

$N a_{0} b - b^{2} = a_{0}^{2} - N$

but since $a_{0} < b$ , this implies:

$N a_{0} b - b^{2} = a_{0}^{2} - N < a_{0} b - N < a_{0} b$

and thus

$N a_{0} b - b^{2} < a_{0} b,$

quod erat demonstrandum.

E.g. using Ruffini:
$\begin{matrix} 1 & - N a_{0} & {a_{0}}^{2} - N \\ b & b & b^{2} - N b a_{0} \\ 1 & b - N a_{0} & b^{2} - N b a_{0} + {a_{0}}^{2} - N = 0 \end{matrix}$
where the reminder is known to be 0 because of equation $(⋆)$ . ↩