Editor's Note: Try the problem yourself before reading on!

As well as solving the original problem, we shall find all solutions of (1). It is convenient to split up the solution into a number of small stages.

Lemma 1. If n=1, the only positive solution of (1) is x = y = 1.

If n = 1, (1) can be written as (y - x) = 1 - xy; the left-hand side is nonnegative, whilst the right-hand side is negative unless x = y = 1.

We shall now assume, unless otherwise stated, that (a,b) is a positive integral solution of (1) for a particular value of n (n > 1), with b a, so that

                              a + b = (ab + 1)n.                           (2)

Lemma 2. b > (n - 1)a.

From (2), b[b - (n - 1)a] = n + a(b - a) > 0, so b > (n - 1)a.

Corollary. b > a.

Lemma 3. b + (nb - a) = [b(nb - a) + 1]n.

This is just a rewriting of (2). Lemma 3 shows that if (a,b) is a solution of (1), then so is (b,nb - a); and b > a, nb - a = (n - 1)b + (b - a) > b, so (b,nb - a) is a strictly greater solution than (a,b).

This lemma provides a method of obtaining a sequence of strictly increasing solutions of (1) when n = k (k > 1), starting with the solution
(k,k). For instance when k = 2 we have (2,8), (8,30), (30,112), ... . The solution (k,k) was originally found by trial and error, but its significance will appear later.

Lemma 4. (na - b) + a= [(na - b)a + 1]n.                            (3)

This is just Lemma 3 with a and b interchanged, and is again a direct consequence of (2). If na - b < 0 then the right-hand side of (3) is nonpositive whilst the left-hand side is positive since a > 0; this is a contradiction. Hence na - b 0. Also na - b < a by Lemma 2, and a < b. Hence (na - b,a) is a positive solution of (1), strictly less than (a,b) unless
na - b = 0.

If we start with any positive solution (a,b) of (1) for a particular value of n, Lemma 4 provides a method of obtaining a sequence of strictly decreasing positive solutions; this is the exact reverse of the previous method of obtaining a strictly increasing sequence. Such a sequence cannot be infinite, so we must reach a positive solution (c,d) in the sequence such that nc - d = 0. Then, from Lemma 4 with (a,b) replaced by (c,d), we deduce that c = n. Hence n is a perfect square, which is what we required to prove, and since c + d = (cd + 1)n we see that d = c.

We have seen that, starting with any positive solution of (1), the decreasing sequence of solutions eventually leads us to the solution (c,c) with n = c; hence every solution with n = c occurs in the increasing sequence starting from (c,c).