Show that the map $\mathbb{Z}_n^*\to \mathbb{Z}_m^*$ is surjective Let $m,n \in \mathbb{Z}$ such that $m|n$. Show that the map $$f: \mathbb{Z}_n^*\to \mathbb{Z}_m^*$$ $$f({a \pmod n}) = (a \pmod m)$$ is surjective. I am not able to figure out any simple way to tackle this... Any hints? 

Got it. Will prove by induction. We just have to show that the result holds when $n=mp$. Let $b \in \mathbb{Z}_m^*$. 
If $b \not\equiv 0 \pmod p$ then $(b,m)=1 \land (b,p)=1 \implies (b,n)=1 \implies b \in \mathbb{Z}_n^*$. Now we have $f(b)=b$. 
If $b \equiv 0 \pmod p$ then $m \not\equiv 0 \pmod p \implies b+m \not\equiv 0 \pmod p$. Therefore $(b+m,p)=1 \land (b+m,m)=1 \implies (b+m,n)=1 \implies b+m \in \mathbb{Z}_n^*$. Now we have $f(b+m)=b$.
The inductive step is straightforward.
