Induction - request for help in proving lemma 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...

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?
