## Making easy things hard

Have you had the experience of having an ingenious proof of something, going through many twists and turns and using surprising results from all over the place, which turned out to be completely unnecessary because a very much simpler argument would do?

Ian Wanless and I needed to know that the following result is true:

Let S be the set of positive integers n with the property that the prime-power factors of n are congruent to 0 or 1 (mod 3). Then, for any positive integer n, there is a member of S between n and n+o(n).

The proof went like this. A theorem of Euler asserts that a prime number p can be written in the form x2+3y2 if and only if it is congruent to 0 or 1 (mod 3). Using this and a multiplicative identity asserting that the product of two numbers of the form x2+3y2 again has this form, it follows that our set S consists of all integers expressible in this form. Now these representatations correspond to integer lattice points lying on a certain ellipse. Using a geometric argument it is easy to see that, if we take the ellipse x2+3y2=n and expand it by a small factor, we catch a new lattice point, and so find a new member of S.

The proof should have gone like this. The set S contains the set of squares, which clearly has the required density property.

But the nice thing is that I don’t have to feel stupid about this. I learned some number theory on the way, and had some good practice in doing estimates using Euclidean geometry.

Even better, the simple argument generalises and proves much more!