Track / Stage 4 / 311 of 340 #1211 of 2604

Problem 1211

AMC 12 late, AIME early

Number theory Difficulty 5.0 Prove it HMMT February · United States

Determine the number of integers $2 \leq n \leq 2016$ such that $n^{n}-1$ is divisible by $2,3,5,7$ .

This one wants a proof. Work it on paper, then read the official solution and mark yourself. Be honest about it: the record is only any use to you if it is.

Official solution

Solution:

Only $n \equiv 1 \pmod{210}$ work. Proof: we require $\gcd(n, 210) = 1$ . Note that for all $p \leq 7$ the order of $n$ $(\bmod\ p)$ divides $p-1$ , hence is relatively prime to any $p \leq 7$ . So $n^{n} \equiv 1 \pmod{p} \Longleftrightarrow n \equiv 1 \pmod{p}$ for each of these $p$ .

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty, ordering) added by this project.