Show that $|(\mathbb Z/p^n\mathbb Z)^* |=p^n-p^{n-1}$.

Question

I'm trying to show that $|(\mathbb Z/p^n\mathbb Z)^* |=p^n-p^{n-1}$.

Then, $$(\mathbb Z/p^n\mathbb Z)^*=(\mathbb Z/p^{n}\mathbb Z)\backslash \{i\mid \gcd(i,p^n)\neq 1\}$$

So I guess that $$|\{i\mid \gcd(i,p^n)\neq 1\}|=p^{n-1},$$ but I have problem to show it, so I'm probably not on the right way.

Any idea ?

Answer 1

It's more easy than you maybe think :

The only numbers $i$ such that $(i,p^n) \neq 1$ are the multiples of $p$ and are exactly $p^{n-1}$ such multiples up to $p^n$ .

This practically is equivalent with $\phi(p^n)=p^n-p^{n-1}$

Answer 2

Hint: the numbers that have non trivial common divisors with $p^n$ must be multiples of $p$ that are smaller than $p^n$...