Let $p$ be prime and let $r$ be a positive integer. How many generators does $\mathbb{Z}_{p^{r}}$ have?

Question

Can someone please help me understand this solution?

Let $p$ be prime and let $r$ be a positive integer. How many generators does $\mathbb{Z}_{p^{r}}$ have?

I do not understand the part that is underlined in red. Why $p^{r}-p$? Because then $gcd(p^{r},p^{r}-p)=p\neq 1$?

Answer 1

$x \in \mathbb{Z}_{p^r}$ is not a generator of $\mathbb{Z}_{p^r}$ iff its order is strictly smaller, that is, iff its order is a proper divisor of $p^r$ (this follows from Lagrange's Theorem). So, to count the number of non-generators of $\mathbb{Z}_{p^r}$, we need to count the number of proper divisors of $p^r$. This is because an element $x \in \mathbb{Z}_{p^r}$ has order properly dividing $p^r$ iff $x$ is relatively prime to $p^r$ (show this!).

The proper divisors of $p^r$ are nothing but all the multiples of $p$ that are strictly smaller than $p^r$. These are nothing but $$ p, 2p, 3p,\dots,(p-1)p, p^2, (p+1)p,\dots,(2p-1)p,2p^2,(2p+1)p,\dots,(p^{r-1}-1)p. $$ Observe that this list is nothing but the set of all multiples of $p$, from $1 \cdot p$ to $(p^{r-1}-1) \cdot p$. The next multiple of $p$ is $p^{r-1} \cdot p = p^r$, but we wanted all proper divisors, so we have omitted this last one.

---

Part of your confusion might stem from the fact that the statement

Note that for $x \in \mathbb{Z}$, $x$ divides $p^r$ if and only if $x$ divides $p$.

is incorrect. For instance, $p^r$ divides $p^r$, but $p^r$ does not divide $p$ if $r > 1$.