$n$ divides $\phi(a^n -1)$ where $a, n$ are positive integer.

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)$ .

Hint for proving that $n \mid \phi(a^n - 1)$ for all integers $n > 0$ and $a > 1$:

1. Find the smallest positive integer $i$ with the property that $$ a^i\equiv1\pmod{a^n-1}.$$
2. Now you know the order of the coset $\overline{a}$ in the group $G=\mathbb{Z}_{a^n-1}^*$. Apply Lagrange's theorem.

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$$