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

Question

Let $p>3$ be a prime. Prove that $24 \mid p^2-1$.

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.

Answer 1

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.

Answer 2

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

Answer 3

$p^2-1 = (p+1)(p-1)$.

$p$ must be either $1$ or $2 \pmod 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\times3= 24$ divides the product.

Answer 4

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

Answer 5

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\,\bmod 8\!:\,\ N = \pm 1, \pm 3 \,\Rightarrow\, N^2\equiv 1$

$\rm\quad\quad\quad N\perp 3 \;\Rightarrow\,\bmod 3\!:\,\ N = \pm 1,\ $ hence $\rm\: N^2\equiv 1$

Thus $\rm\ \ 3, 8\ |\ N^2 - 1 \;\Rightarrow\; 24\ |\ N^2 - 1 \ $ by $\ {\rm lcm}(3,8) = 24,$ by $\,\gcd(3,8)=1,\,$ or by CCRT.

Remark $ $ It's easy to show that $\,24\,$ is the largest natural $\rm\,n\,$ such that $\rm\,n\mid a^2-1\,$ for all $\rm\,a\perp n.$

The Lemma 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 $\rm\,2^{k-1}$

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.

Answer 6

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.

Answer 7

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.

Answer 8

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

Answer 9

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$

Answer 10

If $p\ge 5$ then $(p,3)=1$. By FLT we have $$p^2\equiv 1\pmod3 \implies 3\mid p^2-1.$$ Also , $p\ge 5$ means $p$ is odd and this implies $$p^2\equiv 1\pmod 8\implies 8\mid p^2 -1.$$ We know that $(8,3)=1$; therefore, $24\mid p^2-1$, i.e., $p^2\equiv 1\pmod{24}$.

Answer 11

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.

Answer 12

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

Answer 13

If $p\ge5$ is prime, then $p$ is relatively prime to $24$.

Thus, $p\equiv\pm1, \pm5, \pm7, $ or $\pm11 \mod 24$, so you can see that $p^2\equiv1\mod24$.

Answer 14

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

Answer 15

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

Answer 16

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!

Answer 17

Every prime $\ge 5$ can be expressed in one of the following forms

$$12k+1, 12k+5, 12k+7, 12k+11$$

since $1,5,7,11$ are the numbers less than $12$ and co-prime to $12$. If you square and subtract $1$ to each of the above expression, they are all divisible by $24$.

Answer 18

The other answers are correct and full, but to provide an answer just to the specific narrow question you asked: The special things about $p$ being prime (and $\ge 5$) are first that it will be odd, and second that it will not be divisible by $3$

Hints: The square of any odd number is $\ \equiv 1 \bmod 8$ and the square of any number not divisible by $3$ is $\ \equiv 1 \bmod 3$

I just noticed that HVxvejjw's full answer flows from these hints.

Answer 19

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.