$(\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!!!
 A: 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.
A: 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.
