Prove that $n$ divides $\phi(a^n -1)$ where $a, n$ are positive integer without using concepts of abstract algebra

In general (for $\gcd (a,m)=1)$, if $a_k≡1 \mod m $, then $ord_m(a) ~∣~k.$ In particular, since $a^{ϕ(m)}≡1(\mod m)$, we have $ord_m(a)∣ϕ(m)$. We have $ord_{(a^n−1)}a=n.$

Proof: Let there exist $d< n$ such that $ a^d ≡ 1 \mod(a^n-1) $ .

=> $ (a^n-1)~ |~ (a^d -1)$ which is not possible since $d < n $.

=> $ord _{a^n−1} =n.$

=> $n~|~ \phi(a^n-1)$

Hints/plan of attack:

Undoubtedly you can show that $a$ and $a^n-1$ are coprime (their gcd=1).

We are to count the number of integers $b, 0<b<a^n-1$ such that $\gcd(b,a^n-1)=1$.

Show that if $b$ is such an integer, and $b_1$ is the remainder of $ab$ when divided by $a^n-1$, then $b_1$ also has the property that $\gcd(b_1,a^n-1)=1$.

Now, given such a $b=b_0$, we can form a sequence of numbers $b_1,b_2,\ldots$ such that $b_k$ is the remainder of $ba^k$. Show that the numbers $b_0,b_1,\ldots,b_{n-1}$ are all distinct, but $b_n=b_0$. Thus we have a list of $n$ integers $b_0,b_1,\ldots,b_{n-1}$ all coprime to $a^n-1$.

We can build such lists of $n$ integers starting from any integer coprime to $a^n-1$. Prove that any two such lists have empty intersection.

Well, this proves the claim, doesn't it?