# 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

$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

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.

-

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

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.

-

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.

-

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

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.

-

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$

-

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 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$.

-

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.$

-

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!

-