Alaric's Sieve

The following is a lightly edited note I made for Facebook when I was 18 back in March of 2010 (so first year of universiy). There's been a lot of talk of Oxbridge interviews in my Further Maths class recently and it reminded me of this. Enjoy.

"Right, a bit of background. Back in December, on the train to the Oxford Interviews, I was happily, and rather mindlessly, going through a proof of why the square root of two is irrational. This means that the square root of two can't be written as one integer over another.

I won't go into the proof here since it isn't necessary for the story. But one interesting part of the proof that is needed to propel the story, is as follows:
an odd number squared is an odd number and
an even number squared is an even number.

When reading that you should see that it is at least likely to be true, even by just doing a few examples in your head. But let us show it.
Let's take a generic odd number first. Say (2k+1) where k is any positive number. (We don't care about negative numbers, just put them out of your mind. We are only dealing with nice sensible numbers today.) Let's now square it to see what happens. (2k+1)^2=4k^2+4k+1 which can be written as =2(2k^2+2k)+1 which can be seen as 2*(any number)+1=even+1=odd. So yes, an odd squared is odd.

By doing the same thing for evens, take 2k, square it and see what happens. (2k) ^2=2(2k^2)=even since it is times by 2.

This is all well and good, nice when maths works out. So I had this result out on the train and then I thought, what if I extend this to multiples of 3 rather than two. As a side note, this is best done in modular arithmetic, but I'm keeping it simple to read.

So instead of evens and odds, which could be more helpful described as multiples of two and one more than multiples of two, we have multiples of three, one more than multiples of three and two more than multiples of three. As a short hand I will write them as 3k, 3k+1 and 3k+2. It is crucial to note that every natural number is one of these three things, we call this a partition.

So let's try squaring them.
(3k)^2=3(3k^2) so multiple of three. 
(3k+1)^2=3(k^2+2k)+1 so 1 more than a mult of 3.
(3k+2)^2=3(k^2+4k+1)+1 so 1 more than a mult of 3

Now we notice something odd: non of those results lead to 2 more than a multiple of 3. If we rearrange our logic slightly we can conclude that no square number is two more than a multiple of 3.

So if we got a number line, we could cross out all the numbers 2 more than a multiple of 3 as non of them have a chance of being square numbers.

Brilliant, but at this stage I had arrived at Oxford for my interviews. At one point in my few days there I picked this up again and continued to work with bigger and bigger numbers. So, multiples of 2 didn't cross any out, but 3 did. 4 didn't, but 5 did. eg.
(5k)^2=5(5k^2)
(5k+1)^2=5(5k^2+2k)+1
(5k+2)^2=5(5k^2+4k)+4
(5k+3)^2=5(5k^2+6k+1)+4
(5k+4)^2=5(5k^2+8k+3)+1

So two more and three more than multiples of 5s can't be touched.

Each time we redo this process we eliminate more and more numbers that can't be squares.

A note for effieciency of the method, you don't need to do this method with starting numbers which are non-prime, since they just throw up the same results as their prime factors. So 4 gives the same as 2, 6 gives the same as 2 and 3.

So after the forth iteration we have:

As you can see, the squares are untouched by the colourful destruction around them. I won't go any further with this colouring in lark, but I've tried it on a ten by ten grid before and you get only squares left after a few more iterations.

1 year on in the problem, sitting in a groups, rings and fields lecture, I suddenly realise that it is not complete. How do I know that there isn't some non-square which isn't Sieved out anywhere along the line? I'm sure the prove isn't overcomplicated, but I can't think of it yet.

So at the moment Alaric's Sieve is still a conjecture. A (bizarrely inefficient) method of finding square numbers and only square numbers. Anybody want to prove it?"