I've been searching for an answer to this problem and I haven't found any duplicate, but excuse me if that's the case.
I want to find how many elements generate the cyclic group $\mathbb{Z}/p^r\mathbb{Z}$.
I have already proved that for $\mathbb{Z}/p\mathbb{Z}$ there are $\phi(p)=p-1$ generators, because the order of the coprime numbers to $p$ is exactly $p$.
However I am struggling with the cases $\mathbb{Z}/p^r\mathbb{Z}$ and $\mathbb{Z}/p^rq^s\mathbb{Z}$.
I would appreciate a lot if you could help me with this proof.
Thanks in advanced.
In general, a cyclic group $\mathbb{Z_n}$ (or if you prefer $\mathbb{Z}/n\mathbb{Z}$) has $\phi(n)$ generators. Let's prove it.
Lemma: if $gcd(a,n)=d$ then $\langle a\rangle=\langle d\rangle$ in $\mathbb{Z_n}$.
Proof: $d$ divides $a$ so it's obvious that $a\in\langle d\rangle$ and hence $\langle a\rangle\leq\langle d\rangle$. As for the other direction, note that $d=gcd(a,n)$ and hence there are $k,l\in\mathbb{Z}$ such that $ak+nl=d$. So that way in $\mathbb{Z_n}$ we have $ak=d$, so $d\in\langle a\rangle$ and hence $\langle d\rangle\leq\langle a\rangle$.
Alright, so after we proved the lemma it's very easy to conclude that if $a\in\mathbb{Z_n}$ then $\langle a\rangle=\mathbb{Z_n}$ if and only if $gcd(a,n)=1$. So that way we get that the number of elements which generate $\mathbb{Z_n}$ is $\phi(n)$. For example, if $p$ is a prime then $\phi(p^r)=p^{r-1}(p-1)$ and that is the number of generators.