Exercise 3.2.17 ($n \mid \varphi(p^n - 1)$)

Proof. Since $p\wedge (p^n-1)=1$, $\bar{p}\in {(\mathbb{Z}∕(p^n-1)\mathbb{Z})}^{\times }$. The order of ${(\mathbb{Z}∕(p^n-1)\mathbb{Z})}^{\times }$ is

Let $k\in {\mathbb{Z}}^{+}$. Then

Indeed,

• If $n\mid k$, then $k=\mathit{𝑞𝑛}$ for some integer $q$, thus

  $$p^k-1=p^{\mathit{𝑞𝑛}}-1=(p^n-1)(p^{(q-1)n}+p^{(q-2)n}+\cdots +p^n+1),$$

  therefore $p^n-1\mid p^k-1$.

• Conversely suppose that $p^n-1\mid p^k-1$. Write $k=\mathit{𝑞𝑛}+r$, where $0\le r<n$. Then

  $$p^k-1=p^r(p^{\mathit{𝑞𝑛}}-1)+p^r-1.$$

  Since $p^n-1\mid p^k-1$ and $p^n-1\mid p^{\mathit{𝑞𝑛}}-1$, then $p^n-1\mid p^r-1$, where $0\le p^r-1<p^n-1$, hence $p^r-1=0$ , thus $r=0$ and $n\mid k$.

So the equivalence (1) is proven. This shows that for all $k\in {\mathbb{Z}}^{+}$,

Since $|\bar{p}|$ is the smallest positive integer $k$ such that ${\bar{p}}^k=1$, we obtain

The order of $\bar{p}$ in ${(\mathbb{Z}∕(p^n-1)\mathbb{Z})}^{\times }$ is $n$.

Moreover, by Lagrange’s Theorem, the order of $\bar{p}$ divides $|{(\mathbb{Z}∕(p^n-1)\mathbb{Z})}^{\times }|=\phi (p^n-1)$. Therefore, if $p$ is a prime and $n>0$,

□