# 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". – Leppala Mar 6 '17 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. – Jabernet Mar 5 '17 at 0:51

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

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. – Robert D-B Aug 18 '18 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 '18 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. – mihir patel Aug 19 '18 at 7:25