Let \(a>1\) and \(k>0\) be integers. Prove that \[ k\mid\varphi(a^k-1), \] where \(\varphi\) is Euler’s totient function.
Solution
1. If \(k=1\), the assertion is immediate.
Every integer is divisible by \(1\), so \[ 1\mid\varphi(a-1). \]
2. Assume \(k>1\) and put\[ N=a^k-1. \]Then the residue class of \(a\) is an element of\[ (\ZZ/N\ZZ)^\times. \]
Any common divisor of \(a\) and \(N=a^k-1\) divides both \(a^k\) and \(a^k-1\), hence divides \(1\). Thus \[ \gcd(a,N)=1, \] so \(a\) is invertible modulo \(N\).
3. The order of the residue class of \(a\) in \((\ZZ/N\ZZ)^\times\) is exactly \(k\).
By definition of \(N\), \[ a^k\equiv1\pmod N, \] so the order divides \(k\).
Suppose for some positive \(j<k\) that \[ a^j\equiv1\pmod N. \] Then \[ N\mid a^j-1. \] But \(a>1\) and \(j<k\) give \[ 0<a^j-1<a^k-1=N, \] which is impossible for a positive multiple of \(N\). Hence no positive exponent smaller than \(k\) gives \(1\), and the order is exactly \(k\).
4. One has\[ \boxed{k\mid\varphi(a^k-1)}. \]
The finite group \[ (\ZZ/N\ZZ)^\times \] has order \(\varphi(N)\). By step 3 it contains an element of order \(k\). Lagrange’s theorem therefore gives \[ k\mid |(\ZZ/N\ZZ)^\times| = \varphi(N) = \varphi(a^k-1). \]
5. Q.E.D.
Step 1 handles \(k=1\), and step 4 handles \(k>1\).