Here’s a cute problem that I came across while researching interview brainteasers–supposedly, this is a question asked in interviews by IXL Learning. Suppose is an integer such that and are both prime. Prove that is either or divisible by .
Proof. Suppose . Then since and are prime, we know that and is even, so we only need to show that . The integers belong to distinct residue classes modulo . If , then
Either case contradicts the hypothesis that and are prime.