Search

Puzzle #11: Prove that p^2 – 1 is Divisible by 24 | Google



Prove that p^2 – 1 is divisible by 24 if p is a prime number greater than 3?



Puzzle Solution:

The most elementary proof , without explicitly mentioning any number theory: out of the three consecutive numbers p–1, p, p+1, one of them must be divisible by 3; also, since the neighbors of p are consecutive even numbers, one of them must be divisible by 2 and the other by 4, so their product is divisible by 3⋅2⋅4=24 — and of course, we can throw p out since it’s prime, and those factors cannot come from it.


#InterviewPuzzle #Puzzle #GoogleInterviewPuzzle