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? 

Claim 1:
$\text{ord}_{a^{n}-1}(a) = n$
Proof:
Let $x = \text{ord}_{a^{n}-1}(a)$. Then $a^x-1 \equiv 0 \pmod {a^{n}-1}$. If  $0 < x < n$, then $a^{x} < a^n$ so we are done. 
Claim 2: $n| \phi(a^{n}-1)$.
Proof:
We know that $a^{ \phi(a^{n}-1)} \equiv 1 \pmod { a^{n}-1}$ since $\gcd(a, a^{n}-1) = 1$. Now since the order is $n$, it immediately follows that $n| \phi(a^{n}-1)$.
