# 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 – kaine Feb 13 '15 at 12:01
• Thanks kaine, as per your suggestion, I just posted it also to math.SE – Michael Rize Feb 13 '15 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. – kaine Feb 13 '15 at 12:46
• I'm voting to close this question as off-topic because it belongs on math.SE. – xnor Feb 13 '15 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 '15 at 17:07

## 4 Answers

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? – kaine Feb 13 '15 at 11:59
• Looks like it . – No. 7892142 Feb 13 '15 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. – kaine Feb 13 '15 at 12:40
• someone commented that all resulting numbers are divisible by 24 , not just 3 and 12 .. interesting – Michael Rize Feb 13 '15 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... – kaine Feb 13 '15 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. – kaine Feb 13 '15 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. – PrisonMonkeys Feb 13 '15 at 13:20
• Yep, that was pointed out now on both math.SE and in comments on mine. – kaine Feb 13 '15 at 13:24
• PrisonMonkeys and kaine thanks for the comments, edited my answer with links to your profiles :) – Novarg Feb 13 '15 at 13:29
• 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. – Michael Rize Feb 15 '15 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$...