Yesterday, I came across this prime number factoid:
- Choose any prime number greater than 3
- Square that number
- Add 14
- Divide by 12
The remainder will always be 3.
So I wondered what prime numbers have which is so special for this to always work. I now know that all primes greater than 3 are of the form 6k-1 or 6k+1; this goes nearly all the way to demonstrating this property. But it took me some time to come up with this even more obvious demonstration.
Let us call our prime number p. Saying that p2+14 modulo 12 = 3 is equivalent to saying that p2-1 is divisible by twelve. So all we need to show is that (p-1)(p+1) is divisible by twelve.
For a number to be divisible by twelve, it has to be divisible both by 3 and by 4. We know that, out of p-1, p and p+1, one of them must be divisible by 3 ; and it isn't p, because p is prime. So (p-1)(p+1) is divisible by 3.
p being Prime, we know that p is odd ; therefore, p-1 and p+1 are both even. The product of two even numbers is divisible by 4, so (p-1)(p+1) is divisible by 12.
This property holds true for any p which is odd and not divisible by 3. Also note that of two consecutive even numbers, one of the must be a multiple of four. So (p-1)(p+1) is actually divisible by 24.