One of my colleagues came into my office the other day, and said to me:
If p is prime and greater than 3, prove that p² – 1 is divisible by 24.
Interested readers might want to try this for themselves: it’s not particularly difficult. Of course I started in right away.
Immediately I thought: well, divisibility by 24 means divisibility by 2, by 3 and by 4. Let’s see what we can say about this considering p is odd. i.e. p = 2n + 1. So p² – 1 = (2n + 1)(2n + 1) – 1 = 4n² + 4n. Clearly divisible by 4.
Then I thought: aha. p² – 1 = (p + 1)(p – 1). One of (p + 1), p, (p – 1) is clearly divisible by 3, since these are 3 consecutive numbers. Since p is prime, either (p + 1) or (p – 1) is divisible by 3. Since p is odd, (p + 1) and (p – 1) are both even. And furthermore, since they are consecutive even numbers, one of them must be divisible by 4.
QED.