$(\mathbb{Z}/p^r\mathbb{Z})^{\ast}$ is a cyclic group

I would like to prove that the group $(\mathbb{Z}/p^r\mathbb{Z})^{\ast}$ of the invertible elements of $\mathbb{Z}/p^r\mathbb{Z}$ with $p>2$ prime and $r>0$ is cyclic.

My text suggests to start proving that the kernel $W$ of the canonical homomorphism $(\mathbb{Z}/p^r\mathbb{Z})^{\ast}\to(\mathbb{Z}/p\mathbb{Z})^{\ast}$ is a cyclic group by verifying that $1+p$ has order $p^{r-1}$ in $W$.

I suppose, but I am not sure, that the said canonical homomorphism might be the projection $(\mathbb{Z}/p^r\mathbb{Z})^{\ast}\to(\mathbb{Z}/p\mathbb{Z})^{\ast}:a\mapsto\bar{a}$, and I would say that the kernel of the map is $\{\bar{1}, \overline{1+p},\overline{1+2p}...,\overline{1+(p^{r-1}-1)p}\}$, so it has order $p^{r-1}$ (and therefore if the group generated by $1+p$ has the same order, it must be the kernel itself).

But I haven't been able to prove that $p^{r-1}$ is the least natural number $m$ such that $(\overline{1+p})^{m}=\bar{1}$...

Furthermore, once proved that $W\subset(\mathbb{Z}/p^r\mathbb{Z})^{\ast}$ is cyclic, I don't know how to see that $(\mathbb{Z}/p^r\mathbb{Z})^{\ast}$ is cyclic too... Has anybody got any ideas?

I $\infty$-ly thank you in advance!!!

• I broke up your text a bit (inserting line breaks) to make it a tad more readable. I hope you don't mind. – Namaste Dec 18 '13 at 14:08
• See mathreference.com/num-mod,unm.html for a direct proof that $(\mathbb{Z}/p^r)^*$ is cyclic. If $[\zeta]$ is a generator of $(\mathbb{Z}/p)^*$, then $[\zeta+p]$ is a generator of $(\mathbb{Z}/p^r)^*$. – Martin Brandenburg Dec 18 '13 at 14:29
• See www-groups.mcs.st-and.ac.uk/~neunhoef/Teaching/ff2013/… - Theorem 6.9 - Page 25. It may be help. – AHH Dec 18 '13 at 17:00
• If you expand $(1+p)^m = 1 + \binom m1 p + \binom m2 p^2 + \cdots$ in a binomial expansion, you can show that the power of $p$ dividing $(1+p)^m-1$ is exactly the same as the power of $p$ dividing $\binom m1 p$. That will show you that $p^{r-1}$ is the least such natural number. After that, you should look to general group theory arguments - something like, a finite abelian group with a large cyclic subgroup must itself be cyclic. (By the way, there's an entirely different way to show that these groups are cyclic - see "primitive roots" in number theory.) – Greg Martin Dec 18 '13 at 18:21
• at amWhy: thank you for editing! I am a beginner with formatting here... and Chag Urim sameach! at Martin: very interesting proof and site. at AHH: downloaded the paper, so interesting, but not only because of $\mathbb{F}_p$. at Greg: very elegant way to see that $p^k|(1+p)^m-1\iff p^k|mp$, useful to understand some points behind the mathreference proof. Thank you a lot everybody!!!! – Self-teaching worker Dec 18 '13 at 21:54

For $$r=1$$, you can see that $$\big(\Bbb Z\big/p\Bbb Z\big)^\times$$ is cyclic of order $$p-1$$ by realizing it as the multiplicative group of the finite field $$\Bbb Z\big/p\Bbb Z$$.

Now suppose $$r > 1$$, so that $$\big(\Bbb Z\big/p^r\Bbb Z\big)^\times$$ is an abelian group of order $$p^{r-1}(p-1)$$. Factor $$p-1$$ into primes as $$p-1 = q_1^{s_1}\dotsb q_t^{s_t}.$$

We will prove that each Sylow subgroup of $$\big(\Bbb Z\big/p^r\Bbb Z\big)^\times$$ is cyclic and use the following lemma:

Lemma. Let $$G$$ be a finite group, and let $$P_1,\dots,P_r$$ be its nontrivial Sylow subgroups. If each $$P_i$$ is a normal subgroup of $$G$$, then $$G \cong P_1\times \dotsb \times P_r.$$

Since $$\big(\Bbb Z\big/p^r\Bbb Z\big)^\times$$ is an abelian group, each of its Sylow subgroups is normal, so we will be able to use the Chinese Remainder Theorem (CRT) to conclude that $$\big(\Bbb Z\big/p^r\Bbb Z\big)^\times \cong \Bbb Z\big/p^{r-1}\Bbb Z\times \Bbb Z\big/q_1^{s_1}\Bbb Z\times\dotsb\times\Bbb Z\big/q_t^{s_t}\Bbb Z \underbrace{\cong}_\text{CRT} \Bbb Z\big/p^{r-1}q_1^{s_1}\dotsb q_t^{s_t}\Bbb Z,$$ i.e. that $$\big(\Bbb Z\big/p^r\Bbb Z\big)^\times$$ is cyclic of order $$p^{r-1}q_1^{s_1}\dotsb q_t^{s_t} = p^{r-1}(p-1)$$, as desired.

Proof sketch that the Sylow subgroups are cyclic:

First show that the Sylow $$p$$-subgroup of $$\big(\Bbb Z\big/p^r\Bbb Z\big)^\times$$ is cyclic as follows. Use the Binomial Theorem and induction on $$r$$ to show that if $$p$$ is an odd prime then $$(1+p)^{p^{r-1}}\equiv 1\bmod p^r$$ but $$(1+p)^{p^{r-2}}\not\equiv 1\bmod p^r$$. Deduce that $$1+p$$ is an element of order $$p^{r-1}$$ in $$\big(\Bbb Z\big/p^r\Bbb Z\big)^\times$$. (Recall that if $$g^n = 1$$, then the order of $$g$$ divides $$n$$.) Now we know that the Sylow $$p$$-subgroup of $$\big(\Bbb Z\big/p^r\Bbb Z\big)^\times$$ is cyclic.

Consider the canonical homomorphism $$\varphi\colon\big(\Bbb Z\big/p^r\Bbb Z\big)^\times\to \big(\Bbb Z\big/p\Bbb Z\big)^\times$$ defined by $$a + (p^r)\mapsto a+(p).$$ Note that $$\varphi$$ is a surjection, and that it is indeed the map you specified. By the first isomorphism theorem, $$\frac{p^{r-1}(p-1)}{|\!\ker\varphi|} = \frac{\big|\big(\Bbb Z\big/p^r\Bbb Z\big)^\times\big|}{|\!\ker\varphi|} = \big|\big(\Bbb Z\big/p\Bbb Z\big)^\times\big|=p-1 \implies |\!\ker\varphi| = p^{r-1},$$ hence the kernel of $$\varphi$$ is precisely the Sylow $$p$$-subgroup of $$\big(\Bbb Z/p^r\Bbb Z\big)^\times$$. For each prime $$q\ne p$$ dividing the order of $$\big(\Bbb Z\big/p^r\Bbb Z\big)^\times$$, the Sylow $$q$$-subgroup of $$\big(\Bbb Z\big/p^r\Bbb Z\big)^\times$$ therefore maps injectively into $$\big(\Bbb Z\big/p\Bbb Z\big)^\times$$ under $$\varphi$$, and can thereby be identified with a (cyclic) subgroup of the cyclic group $$\big(\Bbb Z\big/p\Bbb Z\big)^\times$$. Hence we have shown that every Sylow subgroup of $$\big(\Bbb Z\big/p^r\Bbb Z\big)^\times$$ is cyclic. $$\qquad\blacksquare$$

Thus, by the lemma, we may write $$\big(\Bbb Z\big/p^r\Bbb Z\big)^\times$$ as a direct product of its Sylow subgroups, each of which we know to be cyclic: $$\big(\Bbb Z\big/p^r\Bbb Z\big)^\times \cong \Bbb Z\big/p^{r-1}\Bbb Z\times\Bbb Z\big/q_1^{s_1}\Bbb Z\times\dotsb\times\Bbb Z\big/q_t^{s_t}\Bbb Z.$$

By the Chinese Remainder Theorem, since all the primes $$p,q_i$$ are distinct, we have $$\big(\Bbb Z\big/p^r\Bbb Z\big)^\times \cong \Bbb Z\big/p^{r-1}q_1^{s_1}\dotsb q_t^{s_t}\Bbb Z,$$ i.e., that $$\big(\Bbb Z\big/p^r\Bbb Z\big)^\times$$ is cyclic, as desired.

• Where did you use the assumption $p>2$? – Pierre-Yves Gaillard Jul 7 '17 at 15:36
• @Pierre-Yves Gaillard If $r\ge 3$, then $(\Bbb Z/2^r\Bbb Z)^\times$ is not cyclic. Indeed, it has two distinct subgroups of order 2. [cf. Dummit and Foote's Abstract Algebra, Exercise 23 of Section 2.3] – Alex Ortiz Jul 7 '17 at 15:45
• @Pierre-YvesGaillard I realize my previous comment doesn't really answer your question. The assumption $p>2$ is needed to show that the order of $1+p$ is $p^{r-1}$ in $G$. – Alex Ortiz Jul 7 '17 at 15:56
• Very elegant. I have been searching for a proof and I couldn't have found a better one. +1 – Cauchy Aug 14 '17 at 6:59

This is taken from Alan Baker's A Concise Introduction to the Theory of Numbers.

Let $p$ be an odd prime, and let $g$ be a primitive root ($\operatorname{mod}p$). We prove now that there exists an integer $x$ such that $g':=g+px$ is a primitive root ($\operatorname{mod}p^j$) for all prime powers $p^j$. We have $g^{p-1}=1+py$ for some integer $y$ and so, by the binomial theorem, $g'^{p-1}=1+pz$, where $$z\equiv y+(p-1)g^{p-2}x\ (\operatorname{mod}p).$$ The coefficient of $x$ is not divisible by $p$ and so we can choose $x$ such that $(z,p)=1$. Then $g'$ has the required property. For suppose that $g'$ has order $d\ (\operatorname{mod}p^j)$. Then $d$ divides $\phi(p^j)=p^{j-1}(p-1)$. But $g'$ is a primitive root ($\operatorname{mod}\ p$) and thus $p-1$ divides $d$. Hence $d=p^k(p-1)$ for some $k < j$. Further, since is $p$ odd, we have $$(1+pz)^{p^k}=1+p^{k+1}z_k,$$ where $(z_k,p)=1$. Now since $g'^d\equiv1\ (\operatorname{mod}p^j)$ it follows that $j=k+1$ and this gives $d=\phi(p^j)$, as required.