# For any prime $p > 3$, why is $p^2-1$ always divisible by 24?

I know this is very basic and old hat to many, but I love this question and I am interested in seeing whether there are any proofs beyond the two I already know.

-
IIRC, there is a section in Terry Gannon's Moonshine beyond the Monster where he talks about how this fact might be responsible for the appearance of 24 throughout mathematics, particularly in string theory. But I don't have my copy on hand at the moment. – Qiaochu Yuan Jul 28 '10 at 0:10
Thank you Qiaochu. I've pursued your suggestions. Very motivating. – Don De Tina Jul 28 '10 at 0:25
I wonder if there is a proof that starts by considering the finite field with p^2 elements or SL(2,p)? – yatima2975 Jul 28 '10 at 15:09
Oops, missed Pete's answer, so forget about SL(2,p). – yatima2975 Jul 28 '10 at 15:15
Thank you all for your responses. What I've received in insight has far exceeded my expectations. – Don De Tina Jul 28 '10 at 20:04

The most elementary proof I can think of, without explicitly mentioning any number theory: out of the three consecutive numbers $p – 1$, $p$, $p + 1$, one of them must be divisible by $3$; also, since the neighbours of p are consecutive even numbers, one of them must be divisible by $2$ and the other by $4$, so their product is divisible by $3 · 2 · 4 = 24$ — and of course, we can throw $p$ out since it's prime, and those factors cannot come from it.

-
Thanks. Your brain works the same way mine does. – Don De Tina Jul 28 '10 at 0:57
+1: For simple to the point explanation. – Tpofofn Jan 8 '11 at 3:49
awesome. oh, minimum character limit.. uhh... awesome sauce. – Kevin Bourrillion Mar 27 '12 at 23:59
@ShreevatsaR What do you mean by — neighbours of $p$? – Dwayne E. Pouiller Jan 5 '14 at 13:31
@DwayneE.Pouiller: I mean $p-1$ and $p+1$. – ShreevatsaR Jan 5 '14 at 17:04

Consider modulo $24$.. We have $i\mod 24$ for $0\leq i\leq 23$

We have to neglect $a\mod 24$ if $a$ is a multiple of $2$ or a multiple of $3$.. We are left with

• $1\mod 24$
• $5\mod 24$
• $7\mod 24$
• $11\mod 24$
• $13\mod 24\equiv -11\mod 24$
• $17\mod 24\equiv -7\mod 24$
• $19\mod 24\equiv -19\mod 24$
• $23\mod 24\equiv -1\mod 24$

considering squares, we have

• $1^2\mod 24\equiv 1\mod 24$
• $5^2\mod 24\equiv 1\mod 24$
• $7^2\mod 24\equiv 1\mod 24$
• $11^2\mod 24\equiv 1\mod 24$

For same reason as above, squares of below congruence classes are equal to $1\mod 24$.

• $13\mod 24\equiv -11\mod 24$
• $17\mod 24\equiv -7\mod 24$
• $19\mod 24\equiv -19\mod 24$
• $23\mod 24\equiv -1\mod 24$

So, $p^2\equiv 1\mod 24$.

-

Consider any arbitrary integer $a$ such that $2\nmid a$ and $3\nmid a$. Then we must have $a=2q_{1}+1, a=3q_{2}+r_{2}, r_{2}=1$ or $2$. Then $a^{2}-1=4q_{1}^2+4q_{1}=4q_{1}(q_{1}+1)$. Now since if $q_{1}$ is even then $8\mid a^{2}-1$ and if $q_{1}+1$ is even then $8\mid a^{2}-1$ as well, we can conclude in any case $8\mid a^{2}-1$. Now $a^{2}-1=9q_{2}^{2}+6q_{2}r_{2}+r_{2}^{2}-1$. If $r_{2}=1,$ then $r_{2}^{2}-1=0$ then $3\mid a^{2}-1$. If $r_{2}=2$, then $r_{2}^{2}-1=3$ and consequently $3\mid a^{2}-1$ as well. Therefore at the end of the day you have $24\mid a^{2}-1$.

For any prime $p>3$, $p$ by definition is not divisible by $2$ or $3$. Therefore you immediately have $24\mid p^{2}-1$ for any prime $p$.

-
Seriously, do you want to employ such a construed approach for such a simple problem ? . Besides, this question has many nice answers and you are not contributing anything new. Please refrain from answering such old questions. – Shailesh Feb 24 at 6:14
I don't see why you hold a monopoly over the right on this question. And i don't see why you have any right to claim that I am not contributing something new. My proof is new and original. You may not like it and you might be annoyed by an old post being renewed but you are always welcome to unfollow or ignore the post. I will continue answer on old questions as i like. – user162089 Feb 24 at 6:20
Monopoly? Where? You have the right to post this here, but I bet this is one of the two obvious proofs the asker already knew about. Shailesh also has the right to be critical. Or would you prefer a silent downvote? Not that the other answers would go very deep either :-) Relax! – Jyrki Lahtonen Feb 24 at 8:34

$P^2-1 = (P+1)(P-1)$. $P$ must be either $1$ or $(2 \mod 3)$, so we have a factor of $3$ in the product. And $P$ is also either $1$ or $3 \mod 4$.

Hence either $2|(P+1)$ and $4|(P-1)$ or $2|(P-1)$ and $4|(P+1)$.

Thus $8*3= 24$ divides the product.

-

The great clue, I believe, is the perennially useful fact that p^2-1 is (p+1)(p-1). Since p>3, p must be odd and cannot be divisible by three; since there is one number divisible by three in any set of three consecutive numbers either p+1 or p-1 must be divisible by three; and since every other even number is divisible by four, one of these factors must be divisible by two and the other by four. Simple arithmetic follows: 4x3x2=24.

You can expand this effect and demonstrate that if you raise any prime larger than five to the power of four, subtract five times the square of that prime and then add four (I'm chuckling as I type this) you will generate a number divisible by one hundred and twenty without a remainder.

Why anyone would do that, though, is a question for the experts!

-

In fact the result holds a bit more generally, namely:

Lemma $\rm\ \ 24\ |\ M^2 - N^2 \;$ if $\rm \; M,N \perp 6, \;$ i.e. coprime to $6.\;$ The proof is easy:

$\rm\quad\quad\quad N\perp 2 \;\Rightarrow\; N = \pm 1, \pm 3 \pmod 8 \;\Rightarrow\; N^2 = 1 \pmod 8$

$\rm\quad\quad\quad N\perp 3 \;\Rightarrow\; N \;\;= \;\;\;\pm 1\ \pmod 3 \;\Rightarrow\; N^2 = 1 \pmod 3 \;$

So $\rm \quad\; 3, 8\ |\ N^2 - 1 \;\Rightarrow\; 24\ |\ N^2 - 1 \$ since $\ {\rm lcm}(3,8) = 24.$

This is a special case $\rm\ n = 24\$ of this much more general result

Theorem $\$ For naturals $\rm\ a,e,n$ with $\rm\ e,n>1$

$\rm\quad n\ |\ a^e-1$ for all $\rm a\perp n \ \iff\ \phi'(p^k)\:|\:e\$ for all $\rm\ p^k\:|\:n,\ \ p\:$ prime

with $\rm \;\;\; \phi'(p^k) = \phi(p^k)\$ for odd primes $\rm p\:,\$ where $\phi$ is Euler's totient function

and $\rm\ \quad \phi'(2^k) = 2^{k-2}\$ if $\rm k>2\:,\$ else $\,2$

The latter exception is due to $\rm \mathbb Z/2^k$ having multiplicative group $\rm C(2) \times C(2^{k-2})$ for $\rm k>2$.

Notice that the least such exponent $\rm e$ is given by $\rm \;\lambda(n)\; = \;{\rm lcm}\;\{\phi'(\;{p_i}^{k_i})\}\;$ where $\rm \; n = \prod {p_i}^{k_i}\;$.

$\rm\lambda(n)$ is called the (universal) exponent of the group $\rm \mathbb Z/n^*,\;$ a.k.a. the Carmichael function.

So the case at hand is simply $\rm\ \lambda(24) = lcm(\phi'(2^3),\phi'(3)) = lcm(2,2) = 2\:.$

See my post here for proofs and further discussion.

-

Note that any prime $p$ which is $>3$ we have $p-1$ or $p+1$ should be divisible by $3.$ $$(2m+1)^2=4m(m+1)+1\equiv1\mod(8)$$ Hence $p^2-1=(p-1)(p+1)$ is divisible by $3\times 8=24.$

-

We know that every prime $> 3$ is of the form $6n+1$ or $6n-1$. Now find two numbers $a$ and $b$ such that $a+b = p$ and $a-b =1$, where $p$ is either $6n+1$ or $6n-1$. Suppose $p = 6n+1$ Solving $a+b=6n+1$ and $a-b = 1$, we get $a= 3n+1$ and $b=3n$ Thus $ab$ is a multiple of $6$. Therefore $4ab$ is a multiple of $24$. But $4ab = (a+b)^2 – (a-b)^2$. Thus we see that $p^2-1$ is a multiple of $24$.

-

As Unnikrihnan stated, every prime > 3 is of the form 6n + 1, or 6n − 1.

So, we could write the problem as ((6n ± 1)^2 - 1) /24. Solving, we have: ((36n^2 ± 12n +1) – 1)/24;

Which, is equal to (36n^2 ± 12n)/24, and also equal to (3n^2 ± n) / 2, and to
n (3n ± 1) / 2.

Since we are not interested on the numerical value of this equation, but that the result of the equation to be an integer, not a fraction, the n outside of the parenthesis is irrelevant.

So the equation could be written as, (3n ± 1)/2, and the result of this equation is always an integer for any odd or even value of n.

-

We know for every positive integer $n$ , $\sum_{k=1}^n k^2=\dfrac{n(n+1)(2n+1)}6$ . If $p>3$ is a prime then $\dfrac{p-1}2$ is a positive integer , so $$\sum_{k=1}^{\dfrac{p-1}2} k^2=\dfrac{\dfrac{p-1}2\bigg(\dfrac{p-1}2+1\bigg)\Bigg(2\bigg(\dfrac{p-1}2\bigg)+1\Bigg)}6=\dfrac {(p-1)(p+1)p}{24}=\dfrac {p(p^2-1)}{24}$$ ,

so $\dfrac {p(p^2-1)}{24}$ is a sum of some positive integers , and hence an integer i.e. $24$ divides $p(p^2-1)$ , but

also $24=3 ×2^3$ and since $p>3$ is a prime , so $g.c.d (p,24)=1$ , hence $24$ divides $p^2-1$

-

The most basic test one could come up with works easily: clearly with the given hypotheses $p$ must be relatively prime with $24$ (which is really all that matters about $p$) and checking the squares of all $8$ elements of $(\Bbb Z/24\Bbb Z)^\times$ one finds$~1$ each time. I just wanted the obvious to be said.

There are numerous ways to save part of the the work of this computation (using the Chinese remainder theorem $(\Bbb Z/24\Bbb Z)^\times\cong(\Bbb Z/3\Bbb Z)^\times\times(\Bbb Z/8\Bbb Z)^\times$ is one obvious way) but given the tiny amount of work the check is to begin with, there is no real need to elaborate on such savings.

-

Let prime number $p=2k+1$, $p^2-1=4k(k+1)$, then $8|p^2-1$ by theorem, $p^2=1\pmod{3}$, thus $3|p^2-1$ and $24|p^2-1$.

-
Note that the proof works not only for primes but for any integer coprime to 6. It's actually a very special case computation of the Carmichael exponent of $\mathbb Z/n^*$ - see my proof above. – Bill Dubuque Aug 20 '10 at 18:14
hmmmm learnt :) – papadata Aug 21 '10 at 5:07

Here's a very simplistic proof:

$n^2 = 1 \pmod{24}$ for $n=1,5,7,11$, by checking each case individually.

$(n+12)^2 = n^2 + 24n + 144 = n^2 \pmod{24}$.

Therefore, $n^2 = 1 \pmod{24}$ when $n$ is odd and not divisible by $3$, and so $n^2-1$ is divisible by $24$ for these $n$. You don't need primality of $p$ here!

A slight modification would be to use $1$ and $5$ as "base cases", and use the fact that $(n+6)^2 = n^2 + 12n + 36 = n^2 + 12(n+3)$, which is equal to $n^2 \pmod{24}$ when $(n+3)$ is even, i.e. $n$ is odd.

-
@Jodles: I approved your last four suggested edits, but please do take a break from LaTeXing now. Otherwise the front page is flooded by edits from you. As laudable as your efforts are, there are people not exactly in favor of editing very old posts (LaTeX was not available from the beginning). See also this discussion on meta – t.b. Aug 30 '11 at 9:12
@Theo: Sorry, I did not consider that! I will read that discussion. Thank you for letting me know! It was definitely not my intention to flood the front page. (I was going through the list of "low-quality posts" in the review section). – Jodles Aug 30 '11 at 9:15
@Theo: In Jodles' defence, I'm more used to SO's backtick notation and not very good at LaTeX. I'm happy with the edit! (Just as this was falling off the frontpage :) – yatima2975 Aug 30 '11 at 14:53
@yatima2975: Very good, then! I didn't mean to imply Jodles shouldn't do it at all, just act with some restraint, that's all. I'm sure there were no bad intentions whatsoever. – t.b. Aug 30 '11 at 14:56

This is somewhere between an answer and commentary. As others have said, the question is equivalent to showing: for any prime $p > 3$, $p^2 \equiv 1 \pmod 3$ and $p^2 \equiv 1 \pmod 8$. Both of these statements are straightforward to show by just looking at the $\varphi(3) = 2$ reduced residue classes modulo $3$ and the $\varphi(8) = 4$ reduced residue classes modulo $8$. But what is their significance?

For a positive integer $n$, let $U(n) = (\mathbb{Z}/n\mathbb{Z})^{\times}$ be the multiplicative group of units ("reduced residues") modulo $n$. Like any abelian group $G$, we have a squaring map

$[2]: G \rightarrow G$, $g \mapsto g^2$,

the image of which is the set of squares in $G$. So, the question is equivalent to: for $n = 3$ and also $n = 8$, the subgroup of squares in $U(n)$ is the trivial group.

The group $U(3) = \{ \pm 1\}$ has order $2$; since $(-1)^2 = 1$, the fact that the subgroup of squares is equal to $1$ is pretty clear. But more generally, for any odd prime $p$, the squaring map $[2]$ on $U(p)$ is two-to-one onto its image -- an element of a field has no more than two square roots -- so that precisely half of the elements of $U(p)$ are squares. It turns out that when $p = 3$, half of $p-1$ is $1$, but of course this is somewhat unusual: it doesn't happen for any other odd prime $p$.

The group $U(8) = \{1,3,5,7\}$ has order $4$. By analogy to the case of $U(p)$, one might expect the squaring map to be two-to-one onto its image so that exactly half of the elements are squares. But that is not what is happening here: indeed

$1^2 \equiv 3^2 \equiv 5^2 \equiv 7^2 \equiv 1 \pmod 8$,

so the subgroup of squares is again trivial. What's different? Since $\mathbb{Z}/8\mathbb{Z}$ is not a field, it is legal for a given element to have more than two square roots, but a more insightful answer comes from the structure of the groups $U(n)$. For any odd prime $p$, the group $U(p)$ is cyclic of order $p-1$ ("existence of primitive roots"). It is easy to see that in any cyclic group of even order, exactly half of the elements are squares. So $U(8)$ must not be cyclic, so it must be the other abelian group of order $4$, i.e., isomorphic to the Klein $4$-group $C_2 \times C_2$.

More generally, if $p$ is an odd prime number and $a$ is a positive integer, then $U(p^a)$ is cyclic of order $p^{a-1}(p-1)$ hence isomorphic to $C_{p^{a-1}} \times C_{p-1}$, whereas for any $a \geq 2$, the group $U(2^a)$ is isomorphic to $C_{2^{a-2}} \times C_2$. This is one of the first signs in number theory "there is something odd about the prime $2$".

Added: Note that the above considerations allow us to answer the more general question: "What is the largest positive integer $N$ such that for all primes $p$ with $\operatorname{gcd}(p,N) = 1$, $N$ divides $(p^2-1)$?" (Answer: $N = 24$.)

Added Later: I just saw this arxiv preprint which is entirely devoted to the observation made in the previous paragraph. I guess the author does not follow this site...

-
Using a sledgehammer to kill a beetle just looks mental. Take it easy, brother. – Patrick Da Silva May 17 '11 at 3:42
Oh. My mistake. I didn't see the "I am interested in seeing whether there are any proofs beyond the two I already know" part of the question. Then this is a good thing to see. – Patrick Da Silva May 17 '11 at 3:50

One simple, high school level proof:

Every prime number $p>3$ can be written in form $6k \pm 1$. This is easily proved by considering remainders upon dividing by $6$. Using that fact, it suffices to show that any number of that form is going to be divisible by $24$, because that implies that any prime greater than $3$ is going to be divisible by it. Proof uses just a little algebraic manipulation:

$(6k \pm 1)^2 - 1 \Rightarrow 36k^2 \pm 12k + 1 - 1 \Rightarrow 12k(3k \pm 1)$

We use the fact that for every even number times $12$, resulting number is divisible by $24$. So, if $k$ is even then we are done. However, if $k$ is odd, then $3k \pm 1$ is going to be even. Therefore, $k(3k\pm1)$ is even, so we write:

$k(3k\pm1) = 2m \Rightarrow 12\cdot2m \Rightarrow 24m$

Addendum: This above result is just a part of generalised result which we will now prove.

If $p$ is prime number such that $p>0$, then following holds for all natural numbers $n$: $$3 \cdot 2^{2 + n} |\ p^{2^{n}} - 1$$
We are going to prove it using the induction on natural numbers.
The base case, when $n=1$, has already been proven in first part of the post: $3 \cdot 2^{2 + 1} |\ p^{2^{1}} - 1 \Leftrightarrow 24 |\ p^2 - 1$
Suppose that it is valid for $n$: $3 \cdot 2^{2 + n} |\ p^{2^{n}} - 1$, and let us examine case for $n+1$: $$p^{2^{n+1}} - 1 = (p^{2^{n}} - 1)(p^{2^{n}} + 1)$$ By induction hypothesis, we can rewrite this as: $k(3 \cdot 2^{n+2})(p^{2^{n}} + 1)$, for some natural number $k$. Our third term, $(p^{2^{n}} + 1)$, is always going to be even, as power of odd prime will be odd, plus one it will be even, so we can rewrite this as $k(3 \cdot 2^{n+2})2q = 3 \cdot 2^{(n+1) + 2} \cdot kq$, for some natural number $q$. As $3 \cdot 2^{(n+1) + 2} \cdot kq = p^{2^{n+1}} - 1$ for some natural numbers, $k$ and $q$, it follows that $3 \cdot 2^{(n+1) + 2} |\ p^{2^{n+1}} - 1$ and this completes our proof.

-

$p$ must be congruent either to 1,3,5,7 modulo 8. Then $p^2$ is congruent to $1$ modulo $8$ in either case. So $8$ divides $p^2-1$.

Now, $p$ is not a multiple of 3, so either $p-1$ or $p+1$ is a multiple of three. So $3$ divides $p^2-1$.

Together, it follows that 24 divides $p^2 -1$.

-
I hadn't seen this approach previously. Thanks. – Don De Tina Jul 28 '10 at 0:48