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

Question

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?

Answer 1

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

Answer 2

Hint:

$$a^n\equiv 1\pmod {a^n-1}$$ and $$a^d\not\equiv 1\pmod {a^n-1}$$ if $0<d<n$ (why?).

Answer 3

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.