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

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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s