Competition problem — Number theory

Library / /3 of 15

Number theory Difficulty 4.6 AIME Prove it United States

Problem:
Show that $n$ divides $\varphi\left(a^{n}-1\right)$ for any integers $a$ and $n$ , where $\varphi$ is Euler's totient function.

Solution

Solution:
Let $N = a^{n} - 1$ . Then $\gcd(a, N) = 1$ and the order of $a \pmod{N}$ is exactly equal to $n$ . But $a^{\varphi(N)} \equiv 1 \pmod{N}$ too. Thus $n$ divides $\varphi(N)$ .

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

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