1. ## Coprime elements

Let $\displaystyle \mathbb{Z}_{p^r} = \{ 0,1, \ldots, p^r -1\}$ be the ring of integers modulo $\displaystyle p^r$, a power of a prime. I was wondering if someone could help explain why there are $\displaystyle p^{r-1}$ elements that are coprime to $\displaystyle p^r$ in this ring? I am getting tangled up in knots and would appreciate any help with this.

Thanks very much.

2. Originally Posted by slevvio
Let $\displaystyle \mathbb{Z}_{p^r} = \{ 0,1, \ldots, p^r -1\}$ be the ring of integers modulo $\displaystyle p^r$, a power of a prime. I was wondering if someone could help explain why there are $\displaystyle p^{r-1}$ elements that are coprime to $\displaystyle p^r$ in this ring? I am getting tangled up in knots and would appreciate any help with this.

Thanks very much.
In every string of length p of the form $\displaystyle kp, kp+1,\ldots,kp+(p-1)$ there are exactly p-1 numbers coprime with $\displaystyle p^r$, and there are $\displaystyle p^{r-1}$ such strings between $\displaystyle 0\,\,and\,\,p^r$, thus the number is
actually $\displaystyle p^{r-1}(p-1)$ and not $\displaystyle p^r$...

T onio

3. ah sorry i meant, NOT coprime. Thanks very much for your answer, there was a mistake in my notes which was causing confusion but I can see from what you said