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

Question

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

Answer 3

$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 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 \quad 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\:\quad \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.

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