$n\mid \phi(a^{n}-1)$ for any $a>n$?

Question

I saw the proof which goes as follows:

$a^{n} \equiv 1 \pmod{a^{n}-1} $, and $n$ is the smallest power of a such that this is true.

We also know that by Euler's Identity $a^{\phi(a^{n}-1)}\equiv 1\pmod {a^{n}-1}$

So we get $n\mid \phi(a^{n}-1)$.

---

Now I am unable to understand where is the fact that $a>n$ is playing role?

Answer 1

It's not. Nothing in that proof requires $a>n$, and, indeed, the theorem is true for all $a>1,n\geq 1$.

For example, you gave $n=3,a=2$. But then $a^n-1=7$ and $3|\phi(a^n-1)=6$

Answer 2

What we can say is $$ord_{(a^n-1)}a\mid gcd(n,\phi(a^{n}-1))$$

As $ord_{(a^n-1)}a=n, n\mid gcd(n,\phi(a^{n}-1))$

If $a=2,n=5, \phi(2^5-1)=31-1=30$ which is divisible by $5(=n)$.

If $a=2,n=7, \phi(2^7-1)=127-1=126$ which is divisible by $7(=n)$.