Let $p$ be a prime number. Find all possible values of the remainder when $p^{2}-1$ is divided by 12 .
The answers are 3,8 , and 0 .

It is clear that $p=2$ gives $3, p=3$ gives 8 , and $p=5$ gives 0 . We claim that all primes $p \geq 5$ give the remainder 0 as well, i.e. that $p^{2}-1$ is divisible by 12 for these $p$.

We factor:

$$
p^{2}-1=(p+1)(p-1)
$$

Since $p \neq 2, p$ is odd and so $p+1$ and $p-1$ are both even. This gives two factors of 2 in $p^{2}-1$. Moreover, one of the three consecutive integers $p-1, p, p+1$ is divisible by 3 , and since $p \neq 3$, it is not $p$. So either $p-1$ or $p+1$ has a factor of 3 , and so does $p^{2}-1$. Thus $p^{2}-1$ is divisible by $2 \cdot 2 \cdot 3=12$.