Why is every prime number (5 and higher) divisible by 3 when you square it and subtract 1? [closed]

I discovered this by accident, when trying to create a formula that generates prime numbers (an impossible task, I know).

But, I find it very interesting that you take any prime number 5 and greater, then you square it and subtract 1, dividing it by 3 always results in a whole integer.

For example:

5 x 5 = 25 - 1 = 24 / 3 = 8

11 x 11 = 121 - 1 = 120 / 3 = 40

The result is always a whole number, regardless of how high the prime number is.

Can someone explain why this is so, mathematically? This does not seem possible (to me). And if this is really true, why can I find nothing written about it?

I have never heard of this theorem before, and nothing is mentioned on Wikipedia or other sources. But perhaps this could be a helpful in reducing 33% of the possibilities when trying to find or prove large prime numbers, computationally.

UPDATE: someone commented that the resulting number is divisible by 24 , not just 3

• Oh and this might belong better on math.SE Feb 13, 2015 at 12:01
• Thanks kaine, as per your suggestion, I just posted it also to math.SE Feb 13, 2015 at 12:11
• FYI for future use because you are new, per SE guidelines the question should be migrated to math.SE not cross posted. There is no reason for someone to have to work on a question there if it is answered here. Feb 13, 2015 at 12:46
• I'm voting to close this question as off-topic because it belongs on math.SE.
– xnor
Feb 13, 2015 at 17:04
• I know you all mean well, but can we please not answer math problems like this but rather just move them to math.SE? Their community, not ours, is made for this type of thing.
– xnor
Feb 13, 2015 at 17:07

All such primes are of two types: $6x+1$ and $6x-1$ $$(6x+1)^2-1=36x^2+12x$$ $$(6x-1)^2-1=36x^2-12x$$

• Are they all divisible by 12? Feb 13, 2015 at 11:59
• Looks like it . Feb 13, 2015 at 12:06
• @MichaelRize This equation works for all numbers not divisible by 2 and 3. No prime number greater than 3 is divisible by 2 or 3. Feb 13, 2015 at 12:40
• someone commented that all resulting numbers are divisible by 24 , not just 3 and 12 .. interesting Feb 13, 2015 at 12:53
• Actually I hadn't noticed but he is correct: $$36x^2+12x=12x(3x+1)$$ Either $x$ or $3x+1$ are divisible by $2$ so he is correct. I am surprised how many votes this got there... Feb 13, 2015 at 12:59

That happens because when you square a number(let's say $x$), you will get $x^2$ as the result. Then you subtract 1 from it and you get $x^2 - 1$, which can be rewritten as $x^2 - 1^2$ which is then equal to $(x-1)(x+1)$. Prime numbers are only divisible by $1$ and itself($x$).

Also, for any number $x$ the following is true:

$x$, $x+1$ or $x-1$ is fully divisible by 3.

And because $x$ is a prime number, it is not divisible by 3(unless $x = 3$, but you mentioned that it only works for values >= 5).

That product consists of the numbers 1 less than that prime number and 1 more than that prime number. And out of any 3 consequent numbers, 1 is fully divisible by 3, so either $x+1$ or $x-1$ is fully divisible by 3

EDIT

As kaine pointed in his comment, we can also prove that that resulting number $x^2-1$ is also divisible by 12:

If $x$ is prime, it is not divisible by 2(so it's odd). Out of here follows, that both $(x-1)$ and $(x+1)$ are even, thus divisible by 2.

So out of these 2 numbers($(x-1)$ and $(x+1)$) one is divisible by 3 and both are divisible by 2, so the whole number is also divisible by $3*2*2 = 12$

EDIT 2

And as PrisonMonkeys mentioned in the comment, $(x-1)$ and $(x+1)$ are 2 consequent even numbers, so 1 of them is divisible by 4.

That then shows that the whole number $x^2 - 1$ is divisible by $2*3*4 = 24$

• That actually can be used to prove my 12 statement too. It is divisible by 3 as either x+1 or x-1 is divisible by 3. It is divisible by 4 as both x+1 and x-1 are divisible by 2. Ergo it is divisible by 12. Feb 13, 2015 at 12:43
• @kaine It goes even further, see puzzles.nigelcoldwell.co.uk/fifteen.htm, x-1 and x+1 are two consecutive even numbers, so one of them is divisible by 4, which makes $x^2-1$ divisible by 24. Feb 13, 2015 at 13:20
• Yep, that was pointed out now on both math.SE and in comments on mine. Feb 13, 2015 at 13:24
• Your answer is correct, thanks so much for your help. I chose kaine's answer as more correct because of the observation about all primes are 6x + 1 and 6x - 1 , and the fact they are also (later) divisible by 12 and 24. Feb 15, 2015 at 1:07

Each number (without regard of primality), not divisible by $3$ can be expressed as $x + 1$ or $x + 2$ where $x$ is divisible by $3$. In the two cases you have:

$(x + 2)*(x + 2) = x*x + 4*x + 4 = x*x + 4*x + 3 + 1$

Or

$(x + 1)*(x + 1) = x*x + 2*x + 1$

Since $x$ is divisible by $3$ both boil down to

$x*x + 4*x + 3 + 1 = 3*(x/3*x + x/3*4 + 1) + 1 = 3*n + 1$

Or

$x*x + 2*x + 1 = 3*(x/3*x + x/3*2) + 1 = 3*n + 1$

with $n$ being an integer.

3*n + 1

Subtract $1$ and you get a number divisible by $3$.

Since $3$ is the only prime divisible by $3$, this does not work for it. It works for $2$ though. It works for all other primes as well.

Just to reiterate, rehash, and regurgitate what others have pointed out:

• The resulting numbers ($x^2$ - 1), every last dang one of 'em, are divisible not merely by 3, but by $24$ (see the two edits to Novarg's answer)
• Prime numbers (>3) are just a subset of the numbers for which this works: any odd number not divisible by 3; or, any multiple of 6 plus or minus 1: nonprimes $25, 35, 49, 55, 65, 77, 85, 91, 95,$ $115, 119, 121, 125$...