## Cute Modular Arithmetic Brainteaser

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 $n$ is an integer such that $n-1$ and $n+1$ are both prime. Prove that $n$ is either $4$ or divisible by $6$.

Proof. Suppose $n\neq4$. Then since $n-1$ and $n+1$ are prime, we know that $n-1>3$ and $n$ is even, so we only need to show that $3\mid n$. The integers $n-1,n,n+1$ belong to distinct residue classes modulo $3$. If $n\not\equiv 0\pmod{3}$, then

$\displaystyle n-1\equiv0\pmod{3}$ or $\displaystyle n+1\equiv0\pmod{3}$

Either case contradicts the hypothesis that $n-1$ and $n+1$ are prime. $\Box$

This entry was posted in Problem Solving and tagged , , , , , . Bookmark the permalink.