Let and be positive integers such that divides . Why must be a perfect square?

This may be the single most famous elementary number theory problem of recent years, discussed many times on forums such as artofproblemsolving, math.stackexchange and elsewhere. It was also problem 6 of the 1988 IMO.

When I say "elementary" I mean that it can be solved without any advanced techniques that are common in modern number theory. I do not mean to say that it's easy. Several solutions to this problem can be comprehended by anyone with an understanding of basic notions of number theory, but finding those solutions is really, really hard.

How do I know?

Well, the problem was submitted to the IMO problem selection committee by West Germany (I'm guessing Don Zagier may have had something to do with it). Of the six committee members, precisely none could solve it. The problem was then sent to four leading number theorists in Australia, and none of them could solve it either in less than 6 hours. It was classified "superhard" but somehow eventually selected by the jury to be on the competition (those details can be found in Arthur Engel's book "Problem-Solving Strategies").

In the competition, the problem was solved perfectly by just 11 contestants. One of them was Ngô Bảo Châu who went on to win the Fields medal in 2010. Two other solvers were Ravi Vakil who is now an award-winning Stanford mathematician, and the inimitable Zvezdelina Stankova, a renowned researcher and Berkeley Math Circle powerhouse (I can't resist mentioning that Ravi is a fellow board member at Proof School and Zvezda is on the advisory board).

One of the people who didn't solve this problem, believe it or not, was Terry Tao (he may be forgiven - he was only 13 at the time).

This may be a good time to say something about the solution.

Let's restate the problem. We need to show that if a,b are positive integers such that ab+1 divides a^2+b^2, then the quotient \frac{a^2+b^2}{ab+1} is not just an integer - it's a perfect square.

We will use the classical method of infinite descent. This method, usually attributed to Fermat, goes as follows: to show that no positive integer n can have some property, we assume that some such integer does exist, and manipulate the information we have to produce yet another positive integer which A) also has this property and B) is strictly smaller than n. Since we did it once, we can keep doing it over and over again and produce an infinite descending sequence of positive integers. But there is no infinite descending sequence of positive integers. Hence, our original assumption that a positive integer n exists with our property cannot be true.

Another way of restating the same idea is this: if any positive integers exist which have the given property, there must be among them a smallest one. Choose it, call it n, and use it to produce yet another one which is smaller. But this contradicts our original choice of n as the smallest one. Therefore, no positive integers exist with our property.

Back to our problem: of all the possible pairs of positive integers a,b which happen to yield a ratio k=\frac{a^2+b^2}{ab+1} that's not a perfect square, pick one such pair with a+b minimal. If such pairs exist at all, they have various sums a+b, and among all such sums we find the smallest one and fix our pair a,b to yield that minimal sum.

Since the roles of a and b are symmetric in the expression defining k, we may also assume that a \geq b. Otherwise, swap them.

We can rewrite

k=\frac{a^2+b^2}{ab+1}

in the form

a^2-kba+(b^2-k)=0.

In other words, a is a solution of the quadratic equation

X^2-kbX+(b^2-k)=0.

If we have one solution of a quadratic equation, we have to be curious about the other. Let's call this other solution a'. From basic properties of quadratic equations (Vieta's formulas for the very simple case of degree 2), we can determine the sum a+a' and the product aa' quite easily:

a+a' = kb.

aa' = b^2-k.

From the first equation we learn that a' is an integer (This shouldn't be a surprise: a monic integral quadratic either has two integer roots or two irrational ones; it cannot have one integer solution and another that's rational-but-not-an-integer).

From the second equation we learn that a' is not zero. Why? Because remember: k is not a perfect square, so it cannot be equal to b^2.

a' can't be negative, either. If it were, then a'^2-kba'+(b^2-k) (which we know is 0) would be at least a'^2+k+(b^2-k) (we just replaced -kba' with k, which isn't larger when a' is negative), and this is simply a'^2+b^2<0, contradiction.

So now we know that a' is a positive integer. Furthermore, notice that

a' =\frac{b^2-k}{a} < a

because we assumed a \geq b. And finally, since a' was a root of the very same quadratic that a was a root of, we see that the pair a',b yields the same ratio as the pair a,b:

k=\frac{a'^2+b^2}{a'b+1}

and this is a contradiction, because the pair a',b has a smaller sum than the pair a,b which we chose to be minimal. QED