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.

WHY?

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

(6n+1)²= 36n²+12n+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