The Greatest Divisor of p2 − 1 for Primes p > 3

2018 January 23

This was a problem from the Rutgers Undergraduate Mathematics competition in 2017:

Find the greatest natural $n$ which divides all $p^2-1$ for primes $p>3$

And here is my solution, made with the help of Albert Lee and Tom O'Shaughnessy.

Proof: first, we note that, because 5 is a prime greater than 3, then n must divide 52 − 1 = 24, so 1 ≤ n ≤ 24.

Next, we note that p2 − 1 = (p − 1)(p + 1), so we make a number line centered at p:

$$\begin{array}{|c|c|c|c|} \hline p-2& p-1 & p & p+1 \\ \hline \end{array}$$

We note that p cannot be divisible by 2 because it's a prime greater than 2, so p must be odd, so p + 1 and p − 1 are both be divisible by 2. Trivially, exactly 1 of 3 consecutive naturals (e.g. p − 1, p, p + 1) must be divisible by 3, and we know that a prime p > 3 isn't divisible by 3, so exactly one of p − 1 and p + 1 is divisble by 3. Now, we note that exactly 1 of 4 naturals must be divisible by 4, so one of p − 2, p − 1, p, p + 1 must be divisible by 4. However, p and p − 2 are both odd, so they can't be divisible by 4, so exactly one of p − 1 and p + 1 is divisible by 4.

Now, we've established that, among p − 1 and p + 1, both are divisible by 2, exactly one is divisible by 3, and exactly one is divisible by 4. Thus, (p − 1)(p + 1)=p2 − 1 must be divisible by 2 twice, 3 once, and 4 once, so it's divisible by 22 ⋅ 3 ⋅ 4 = 24. This is true for any prime p > 3. We've already established that n ≤ 24, so now that we've established that 24 divides p2 − 1 for all primes p > 3, we've proven that the greatest such n is 24. $\blacksquare$

As a closing remark, note that the same argument could be made using
$$\begin{array}{|c|c|c|c|} \hline p-1 & p & p+1 & p+2 \\ \hline \end{array}$$
by replacing every p − 2 with p + 2 in the proof.