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

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}$

• Check out "Euler's phi function". Mar 6, 2017 at 9:33

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.

• Okay I think that helps, I was reading the $p^r$ wrong. Mar 5, 2017 at 0:51

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).$$

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$$

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.

• Please format your post with MathJax.Also, this formula is hinted at by the currently accepted answer. If you added more details, such as how you derived this, then it may be helpful. Aug 18, 2018 at 14:39
• It will be more helpful if you can give details regarding how you arrived at your formula. As it stands, this answer should be a comment.
– user279515
Aug 18, 2018 at 15:06
• Actually I do not know how to prove this because I derived this formula using patterns i.e. by doing trial and error till p=5. Aug 19, 2018 at 7:25