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 5^{2} − 1 = 24, so 1 ≤ *n* ≤ 24.

Next, we note that *p*^{2} − 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)=*p*^{2} − 1 must be divisible by 2 twice, 3 once, and 4 once, so it's divisible by 2^{2} ⋅ 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 *p*^{2} − 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.