Find the number of generators of the cyclic group $\mathbb{Z}_{p^r}$

Question

Let $p$ be a prime number. Find the number of generators of the cyclic group $\mathbb{Z}_{p^r}$, where $r \in \mathbb{Z} \geq 1$

I'm trying to understand the question and am experimenting with $p=5$ and $r=1,2,3$.

When $r=1$ it generates $\mathbb{Z_5}$, where every non-zero element is a generator of the group.

When $r=2$ it generates $\mathbb{Z_{10}}$. All the elements relatively prime to $10$ are $1,3,7,$ and $9$, also $4$ generators.

When $r=3$ it generates $\mathbb{Z_{15}}$. All of the elements relatively prime to $15$ are $1,2,4,7,8,11,13$, and $14$, which are $8$ generators.

So I'm trying to figure out how to find the number of relatively prime elements for the general group $\mathbb{Z}_{p^r}$

Answer 1

You have the right idea, but remember it's $p^r$, not $pr$. So for instance, for $p=5$ and $r=2$, you get $\mathbb{Z}_{25}$, not $\mathbb{Z}_{10}$.

This also makes the question easier to answer: you just have to count how many integers between $1$ and $p^r$ are relatively prime to $p^r$. An integer is relatively prime to $p^r$ iff it is not divisible by $p$ (why?). To count such integers, you may find it easier to first count the integers between $1$ and $p^r$ that are divisible by $p$. I'll let you finish from here.

Answer 2

I personally would use the prime counting function as follows: $$ \pi(p^r)−\pi(1),$$ with $$\pi(x) ∼ \frac{x}{\log(x)},$$ so that the number of generators for the cyclic group $\mathbb{Z}_{p^r}$ is given by $$z(p^r)=\pi(p^r)−\pi(1).$$

Answer 3

Whe have $\mathbb{Z}_{p^r} = \{0,1,2,\,\dots,\;p^{r}-1\}$ with $p^r$ elements.

We want elements $n \in \mathbb{Z}_{p^r}: \gcd(n,p^r)=1.$

Example of why $\gcd = 1:\; p=2 \text{ and } r=3.$
So $\mathbb{Z}_{2^3} = \{0,1,2,3,4,5,6,7\}$ if $n=2$,
and $\gcd(2,8)= 2\;\;\Rightarrow\;\; \langle 2\rangle \neq \mathbb{Z}_{2^3}.$
If $n=3,\; \gcd(3,8) = 1 \;\;\Rightarrow\;\; \langle 3\rangle = \mathbb{Z}_{2^3}.$

But $p^r$ has $p^{r-1}$ divisors, and therefore we have $p^r - p^{r-1}$ generators in $\mathbb{Z}_{p^r}.\;\;\blacksquare$

Answer 4

I think the formula to calculate the answer of above question is $p^r-p^{r-1}.$ Please re-check it and if there is counter example then notify me.