Choose a prime number greater than 3.
Multiply it by itself and add 14.
Divide by 12 and write down the remainder.
It will always be 3.
All primes greater than 3 are not divisible by 2 so the primes must be odd
All primes greater than 3 are not divisible by 3 so primes after this are of the form 6n+1 or 6n-1
add 14 to this to get 36n²+12n+15
Now dividing by 12: the first two terms give no remainder but the last gives a remainder of 3.
6n-1 works the same way.
Incidentally this proof shows the trick isn't so much about primes as about numbers divisible by neither 2 nor 3. You can check it works with the composites such as 25, 35, 49, etc.
Posted by Jer
on 2010-09-30 15:49:41