# In $(\mathbf Z/p^r \mathbf Z)^*$, finding an element with order $p-1$.

Let $p$ be an odd prime number.
I want to prove that $(\mathbf Z/p^r \mathbf Z)^*$ is an cyclic group.
I have known that $\overline {p-1} \in (\mathbf Z/p^r \mathbf Z)^*$ is of order $p^{r-1}$.
Since the order of the group is $(p-1)p^{r-1}$, if we find an element with order $p-1$, we conclude that $(\mathbf Z/p^r \mathbf Z)^*$ must have an element with order $(p-1)p^{r-1}$.

$\because$ Every finite commutive group has an element with order of its exponent.

So how to I find the existence of an element with order $p-1$?

I think it is possible by induction, for $r=1$ it is the classical result I assume to be true.

Take $0\leq x\leq p-1$ such that $x$ is of order $p-1$ in $\mathbb{Z}/p \mathbb{Z}^*$. We will be looking for an element of order $p-1$ in $\mathbb{Z}/p^2 \mathbb{Z}^*$ under the form :

$$x_2=x+\alpha p$$

Where $\alpha$ is to be determined, we have :

$$x_2^{p-1}=x^{p-1}+(p-1)\alpha x^{p-2} p\text{ mod } p^2$$ $$x_2^{p-1}=x^{p-1}-\alpha x^{p-2} p\text{ mod } p^2$$

Now because $x$ is of order $p-1$ we have $x^{p-1}=1+t_1p$ hence :

$$x_2^{p-1}=1+(t_1-\alpha x^{p-2}) p\text{ mod } p^2$$

Hence $\alpha$ must verify the equation $t_1-\alpha x^{p-2}=0$ mod $p$. This is clearly solvable because $x^{p-2}$ can be inversed mod $p$, hence one can construct $\alpha$ such that :

$$x_2:=x+\alpha p\text{ is of order dividing } p-1$$

Now $x_2=x$ mod $p$ so its order must be divided by the order of $x$ mod $p$ which is $p-1$ hence $x_2$ is exactly of order $p-1$.

Assume now that $x_{r-1}$ is of order $p-1$ in $\mathbb{Z}/p^{r-1} \mathbb{Z}^*$ then define :

$$x_r:=x_{r-1}+\alpha p^{r-1}$$

Likewise, this define an element in $\mathbb{Z}/p^{r} \mathbb{Z}^*$ and :

$$x_r^{p-1}=x_{r-1}^{p-1}+(p-1)\alpha x_{r-1}^{p-2} p^{r-1}\text{ mod } p^r$$

$$x_r^{p-1}=x_{r-1}^{p-1}-\alpha x_{r-1}^{p-2} p^{r-1}\text{ mod } p^r$$

But $x_{r-1}^{p-1}=1+t_{r-1}p^{r-1}$ hence we have that :

$$x_r^{p-1}=1+(t_{r-1}-\alpha x_{r-1}^{p-2}) p^{r-1}\text{ mod } p^r$$

Now the equation in $\alpha$ : $t_{r-1}-\alpha x_{r-1}^{p-2}=0$ mod $p$ is solvable hence one can find $\alpha$ such that $x_r$ is of order dividing $p-1$, now by construction $x_r$ mod $p^{r-1}$ is $x_{r-1}$ hence its order must be divided by $p-1$, finally $x_r$ is an element of order $p-1$ in $\mathbb{Z}/p^r \mathbb{Z}^*$.

• I appreciate your answer. It is very good. – Jeong Jun 12 '15 at 11:16