## Dividing Prime

Pick any prime number greater than three. Find one less than the square of that prime number. What is the greatest positive integer that must be a divisor of the result?
Source: mathcontest.olemiss.edu 10/10/2011

SOLUTION
Let $p$ be a prime number greater than three. The table below lists the value of $p^2-1=\left (p+1\right )\left (p-1\right )$ for some prime numbers.

The table suggests that 24 is the greatest positive divisor of $p^2-1$. The presence of the two consecutive even factors $\left (p+1\right )$ and $\left (p-1\right )$ gives us ideas on how to prove the conjecture.
Since $24=2\times 2\times 2\times 3$, we want to show that at least three 2s and one 3 come from the product $\left (p+1\right )\left (p-1\right )$

Idea 1
$2\times 2$ is easy to see because both $\left (p+1\right )$ and $\left (p-1\right )$ are even and each contributes one 2.

Idea 2
If $a$ and $b$ are two consecutive even numbers, then 4 divides either $a$ or $b$.
Proof
If 4 divides $a$, we are done.
If 4 does not divide $a$, then there exist a quotient $q$ and a remainder $r$ such that
$a=4q+r$,    $r=1,2,3$
If $r=1$ or $r=3$
$a=4q+1$ or $a=4q+3$
This is not possible because in either case the right-hand side is an odd number and $a$ is even.
If $r=2$
$a=4q+2$
$b=a+2$
$=\left (4q+2\right )+2$
$=4q+4$
$=4\left (q+1\right )$
The last equation shows that 4 divides $b$. DONE.

Applying Idea 2
$\left (p+1\right )$ and $\left (p-1\right )$
are two consecutive even numbers, thus 4 divides either one of them. So we pick up an additional 2 to have $2\times 2\times 2$.

Idea 3
If $a,b,c$ are three consecutive positive integers, then 3 divides one of them.
Proof
If 3 divides $a$, we are done.
If 3 does not divide $a$, then there exist a quotient $q$ and a remainder $r$ such that
$a=3q+r$,    $r=1,2$
If $r=1$
$a=3q+1$
$c=a+2$
$=\left (3q+1\right )+2$
$=3q+3$
$=3\left (q+1\right )$
The last equation shows that 3 divides $c$.
If $r=2$
$a=3q+2$
$b=a+1$
$=\left (3q+2\right )+1$
$=3q+3$
$=3\left (q+1\right )$
The last equation shows that 3 divides $b$. DONE.

Applying Idea 3
$\left (p-1\right ),p,\left (p+1\right )$ are three consecutive positive integers, thus 3 divides either $\left (p-1\right )$ or $\left (p+1\right )$ and not $p$ because it is a prime number. So we pick up a factor 3 to finally have $2\times 2\times 2\times 3$.

Therefore, 24 is the greatest positive integer that divides $p^2-1$.