Induction - request for help in proving lemma

Question

Could anyone help with proving the following lemma, please?

Let: $n\in \mathbb{N}$, $Z_{n}^{*}:=\{k\in\mathbb{N}: k\in\{1,\dots,n\} \wedge \space GCD(k,n)=1\}$. Then: $\forall n\in \mathbb{N} \space \forall p \in \mathbb{P}: |Z_{p^{n}}^{*}|=p^{n}-p^{n-1}$

I tried to prove this by induction with respect to $n$, but I stuck at general case. I know how induction works, but I can't see how to do main point...

Answer 1

You may be overthinking it. ${\rm gcd \ }(k,p^{n}) = 1$ holds if and only if $k$ is not divisible by $p$.

So you need to count the number of elements in $\mathbb Z_{p^n}$ that are not divisible by $p$.

Ask yourself:

(1) How many elements are there in $\mathbb Z_{p^n}$ in total?

(2) What fraction of these elements are divisible by $p$ and what fraction are not?