Prove that $n$ divides $\phi(a^n-1)$, where $\phi$ is Euler's $\phi$-function. Let a, n be positive integers. Prove that n divides $\phi(a^n-1)$, where $\phi$ is Euler's $\phi$-function.
I know this problem can be done using number theory approaches, however I am rusty on those concepts can someone help me? 

Since the problem was also flagged under abstract algebra, a group-theoretic approach. This problem was posed in the section of Topics in Algebra (Herstein) on automorphisms, so:
Let $G$ be a cyclic group of order $a^n - 1$. The automorphism group $\mathcal{A}(G)$ is isomorphic to $U_{a^n - 1}$, the group of integers relatively prime to $a^n - 1$. Thus $|\mathcal{A}(G)| = \varphi(a^n - 1)$. 
Every $T\in \mathcal{A}(G)$ is of the form $T_{s} (g) = g^s$ for $s<a^n - 1$ with $\gcd(s, a^n - 1) = 1$. Check that the set $\{ T_a, T_{a^2}, \cdots, T_{a^n} \}$ is a subgroup of $\mathcal{A}(G)$. By Lagrange's Theorem, it follows $n \vert \varphi(a^n - 1)$. 
