$n$ divides $\phi(a^n -1)$ where $a, n$ are positive integer. 
Let $n$ and $a$ be positive integers with $a > 1$. I need to show that $n$ divides $\phi(a^n -1)$.

Here, $\phi$ denotes the Euler totient function.
Could any one give me a hint?
 A: Hint:
$$a^n\equiv 1\pmod {a^n-1}$$
and $$a^d\not\equiv 1\pmod {a^n-1}$$
if $0<d<n$ (why?).
A: Hint for proving that $n \mid \phi(a^n - 1)$ for all integers $n > 0$ and $a > 1$:


*

*Find the smallest positive integer $i$ with the property that
$$ a^i\equiv1\pmod{a^n-1}.$$

*Now you know the order of the coset $\overline{a}$ in the group $G=\mathbb{Z}_{a^n-1}^*$. Apply Lagrange's theorem.

A: You can apply Euler's Theorem like this:
$${a}^{\phi\left(m^n-1\right)}\equiv 1 \pmod{m^n-1}$$
Also, you can use this fact:
$$\left(x^a-1,x^b-1\right)=x^{\left(a,b\right)}-1$$
A: $a$ has multiplicative order $n$ in the ring of integers modulo $a^n - 1$, but this order must divide the order of the group of units modulo $a^n - 1$.
A: A group theoretic solution can be given, (though this solution requires some advanced concepts yet it is very elegant and beautiful).
Let $m= a^n-1$.
Consider the group $G = (\mathbb{Z} / m\mathbb{Z})^*$ or rather $(\mathbb{Z}_m)^*$.
This group has $\phi(m)$ elements or rather the order of the group is $\phi(m)$.
Let $\bar a \in \mathbb{Z} / m \mathbb{Z}$ be the remainder class of the integer $a$ modulo $m$. Then, $\bar a \in G$, as $\gcd(a,m) = \gcd(a,a^n-1)=1$.
Consider the subgroup $H=\left<\bar a\right>$ that is the subgroup generated by $\bar a$.
Now $a^n\equiv 1 \mod m$ (where $m=a^n-1$ and $n$ is the smallest integer with this property), but no positive integer $i<n$ satisfies $a^i \equiv 1 \mod m$ (since $a^i - 1$ is a positive integer smaller than $m$). This implies that order of $H$ equals $n$.
Now as the order of a subgroup always divides the order of a group we have $n\mid\phi(a^n-1)$ .
A: 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 of $a$ is $n$, it immediately follows that $n| \phi(a^{n}-1)$.
