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?

Solution 1:

Since the problem was also flagged under abstract algebra, a group-theoretic approach. This problem was posed in the section of Topics in Algebra (Herstein) on automorphisms, so:

Let $G$ be a cyclic group of order $a^n - 1$. The automorphism group $\mathcal{A}(G)$ is isomorphic to $U_{a^n - 1}$, the group of integers relatively prime to $a^n - 1$. Thus $|\mathcal{A}(G)| = \varphi(a^n - 1)$.

Every $T\in \mathcal{A}(G)$ is of the form $T_{s} (g) = g^s$ for $s<a^n - 1$ with $\gcd(s, a^n - 1) = 1$. Check that the set $\{ T_a, T_{a^2}, \cdots, T_{a^n} \}$ is a subgroup of $\mathcal{A}(G)$. By Lagrange's Theorem, it follows $n \vert \varphi(a^n - 1)$.

Solution 2:

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

Solution 3:

Here's a fun (non-pedagogical) proof of $f\mid\varphi(q^f-1)$ when $q$ is a prime power: ${\rm Gal}(\Bbb F_{q^f}/\Bbb F_q)$ acts on the generators of $\Bbb F_{q^f}^\times$ with trivial stabilizers, hence the claim follows from orbit-stabilizer. In fact the quotient $\varphi(q^f-1)/f$ counts the number or primitive polynomials of degree $f$ in $\Bbb F_q[x]$.