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 ab+1 divides a2+b2. Show that

a2+b2ab+1

is the square of an integer.

The solution

Let

f(x,y)=x2+y2xy+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)=a2 and f(0,b)=b2.

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

Let us then prove the existence of a1. Let N=f(a0,b). By hypothesis, N is an integer and we have

a02+b2a0b+1=N

that with simple algebra can be rearranged into

b2-Na0b+a02-N=0.  ()

This implies that the quadratic equation

x2-Na0x+a02-N=0

has the solution x=b. Dividing the polynomial

x2-Na0x+a02-N

by x-b gives us1 the second root, a1=Na0-b, which again is an integer.

We need to show that a1<a0, i.e.

Na0-b<a0

or equivalently

Na0b-b2<a0b.

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

Na0b-b2=a02-N

but since a0<b, this implies:

Na0b-b2=a02-N<a0b-N<a0b

and thus

Na0b-b2<a0b,

quod erat demonstrandum.


  1. E.g. using Ruffini:

    1 -Na0 a02-N b b b2-Nba0 1 b-Na0 b2-Nba0+a02-N=0 where the reminder is known to be 0 because of equation (). ↩