# Showing that $(\mathbb{Z}/p^a \mathbb{Z})^*$ has order $p^{a-1}(p-1)$.

Showing that $(\mathbb{Z}/p^a \mathbb{Z})^*$ has order $p^{a-1}(p-1)$ where $p$ is prime.

This for a class on elementary number theory, so this question caught me off-guard having only minor experience with group theory. I have a feeling I'll need to use Lagrange for this one, but not sure where to start exactly. Any thoughts?

• The number of elements of this group is the same as the number of $n$ between $1$ and $p^a$ that are coprime to $p^a$. How many such numbers are there? Hint: What numbers aren't coprime to $p^a$? – fretty Nov 5 '12 at 18:42
• The elements of $(\Bbb Z/p^a\Bbb Z)^*$ are just the (equivalence classes) of integers in $\{1,\dots,p^1-1\}$ that are relatively prime to $p^a$: those are the only ones in $\Bbb Z/p^a\Bbb Z$ that have multiplicative inverses. It’s just a problem about the Euler totient function $\varphi$. – Brian M. Scott Nov 5 '12 at 18:42

## 2 Answers

$\mathbb Z/p^r\mathbb Z$ has $p^r$ elements.

$(\mathbb Z/p^r\mathbb Z)^\times$ is a subset, having removed all the non-invertible elements: that is exactly the multiples of $p$. Those are $p,2p,3p,\ldots,p^{r-1}p$ so there are $p^{r-1}$ of them.

So there are $p^r - p^{r-1} = p^{r-1}(p-1)$ units in $\mathbb Z/p^r\mathbb Z$.

We can extend this to $\mathbb Z/ab\mathbb Z$ where $(a,b) = 1$, by chinese remainder theorem this is isomorphic to $\mathbb Z/a\mathbb Z \times \mathbb Z/b\mathbb Z$ so has the same number of units, hence $|(\mathbb Z/ab\mathbb Z)^\times|=|(\mathbb Z/a\mathbb Z)^\times||(\mathbb Z/b\mathbb Z)^\times|$.

One defines the Euler totient function $\varphi(n) = |(\mathbb Z/n\mathbb Z)^\times|$ and we have

• $\varphi(p^r) = p^{r-1}(p-1)$
• $\varphi(ab) = \varphi(a)\varphi(b)$ when $(a,b)=1$
• reading through this again, I really like the first argument. thanks! – user45793 Nov 8 '12 at 18:56

This is just the totient function