Exercise 2.8.33 ($k$ divides $\phi(a^k - 1)$)

Proof. Let $m=a^k-1$, where $k\ge 1,a\ge 2$. Then $a^k\equiv 1(\mathit{mod}m)$. Moreover, for all positive integer $n$, if $a^n\equiv 1(\mathit{mod}m)$, then $a^k-1\mid a^n-1$, where $a^n-1\ne 0$, thus $a^k-1\le a^m-1$. Hence $k\le m$ (if $k>m$, then using $a\ge 2$, $a^k>a^m$, thus $a^k-1>a^m-1$). This shows that the least positive integer $n$ such that $a^n-1\equiv 1(\mathit{mod}m)$ is $k$, so the order of $a$ modulo $m$ is $k$.

Since $m=a^k-1$ is prime to $a$, by Euler’s Theorem, $a^{\varphi (m)}\equiv 1(\mathit{mod}m)$. Therefore the order of $a$ modulo $m$ divides $\varphi (m)$, so

□