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

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?

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

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

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.
• Dear Jyrki! Nice and simple group-theoretic proof! +1
– RFZ
Jan 7, 2018 at 16:29

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

• Hello Issac Yiu! Welcome to MSE! Aug 11, 2019 at 5:34
• ...lol,hahahaha Aug 11, 2019 at 6:00

$$a$$ has multiplicative order $$n$$ in the ring of integers modulo $$a^n - 1$$, but this order must divide the order of the group of units modulo $$a^n - 1$$.

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 of $$a$$ is $$n$$, it immediately follows that $$n| \phi(a^{n}-1)$$.