Exercise 2.3.21 (The order of $1+p$ is $p^{n-1}$ in $(\mathbb{Z}/p^n \mathbb{Z})^\times$)

Proof. Note first that for all integers $a$ and for all integers $k\ge 1$.

Indeed, by the Binomial Theorem,

Since $p$ is an odd prime, $p>2$, hence $p\mid \left(\genfrac{}{}{0.0pt}{}{p}{2}\right)$, thus $p^{2k+1}\mid \left(\genfrac{}{}{0.0pt}{}{p}{2}\right)p^{2k}{a}^2$, and $2k+1\ge k+2$ because $k\ge 1$, so

Moreover, for $i\ge 3$, $p^{3k}\mid \left(\genfrac{}{}{0.0pt}{}{p}{i}\right)p^{\mathit{ik}}{a}^i$, and $3k\ge k+2$ because $k\ge 1$, so

This shows that (1) is true.

Now we show by induction on $k\ge 1$ the property $𝒫(k)$, where

• If $k=1$, then

  $${(1+p)}^{p^{k-1}}={(1+p)}^{p^0}=1+p=1+p^k,$$

  so $𝒫(1)$ is true.

• Suppose that $𝒫(k)$ is true for some integer $k\ge 1$. Then ${(1+p)}^{p^{k-1}}=1+p^k+\lambda p^{k+1}$ for some integer $\lambda$. Therefore

  $$\begin{array}{llllll}\hfill {(1+p)}^{p^k}& ={({(1+p)}^{p^{k-1}})}^p& \hfill & & \hfill & \\ \hfill & ={(1+p^k(1+\mathit{\lambda p}))}^p& \hfill & & \hfill & \\ \hfill & \equiv 1+p^{k+1}(1+\mathit{\lambda p})(\mathit{mod}{p}^{k+2})& \hfill (\text{by (1), where }a=1+\mathit{\lambda p}\text{)}& & \hfill & & \hfill \\ \hfill & \equiv 1+p^{k+1}(\mathit{mod}{p}^{k+2})& \hfill & & \hfill & \end{array}$$

  so $𝒫(k+1)$ is true.

• The induction is done, which proves that for every prime number $p>2$,

  $$\forall <!--\; FUNCTION\; APPLICATION\; -->k\ge 1,{(1+p)}^{p^{k-1}}\equiv 1+p^k(\mathit{mod}{p}^{k+1}).$$

In particular, for every integer $n\ge 2$, since $p^n\mid p^{n+1}$,

Then the order $d$ of $1+p$ in the group ${(\mathbb{Z}∕p^n\mathbb{Z})}^{\text{×}}$ satisfies $d\mid p^{n-1}$ but $d\nmid p^{n-2}$, hence $d=p^{n-1}$.

(Note that the order of $1+p\equiv 1(\mathit{mod}p)$ is $1=p^0$ in ${(\mathbb{Z}∕\mathit{p\mathbb{Z}})}^{\text{×}}$, so the property remains true if $n=1$.)

In conclusion, for every positive integer $n$, $1+p$ is an element of order $p^{n-1}$ in the multiplicative group ${(\mathbb{Z}∕p^n\mathbb{Z})}^{\text{×}}$. □