Proving a function $\pi$ from $U(q) \to U(q')$ to be onto This particular question was asked in my abstract algebra quiz and I could not solve it.

Let $q ,q' \in \mathbb{N} $ and let $q'\mid q$ . Let $U(m)$ denote the multiplicative group of residue classes coprime to $m$ . Let $\pi: U(q) \to U(q')$ be such that if $a \in U(q)$, $\pi(a)$ is unique element in $U(q')$ such that $a \equiv \pi(a) \pmod {q'}$.

Then show that $\pi$ is onto.
Attempt - I was confused. All I could show is that $a$ is non zero as $a$ belongs to $U(q)$ and $a \not \equiv 0 \pmod {q'}$ as $\pi(a) \not \equiv 0 \pmod {q'}$ . But clearly then are not sufficient to prove onto.
Kindly, just give some hints. Rest I would like to work by myself.
 A: Hint: Let $y\in\Bbb Z$ such that $\gcd(y,q')=1$.
By Chinese Remainder Theorem there exists $k\in\Bbb Z$ such that $y+kq'\equiv 1\pmod p$ for every prime divisor $p$ of $q$ which doesn't divide $q'$.

Detailed proof: Let $P$ be the set of prime divisors of $q$ which doesn't divide $q'$.
By Chinese Remainder Theorem there exists $k\in\Bbb Z$ such that
$$k\equiv(1-y)q'^{p-2}\pmod p$$
for every $p\in P$.
For every $p\in P$, from $p\nmid q'$ follows $q'^{p-1}\equiv 1\pmod p$, hence $y+kq'\equiv 1\pmod p$.
Note that $\gcd(y+kq',q)=1$.
For let $p$ be a prime divisor of $\gcd(y+kq',q)$.
Then $p|q$.
If $p|q'$, then $p|y$ which contradicts $\gcd(y,q')=1$.
Otherwise, if $p\nmid q'$, then $p\in P$, hence $y+kq'\equiv 1\pmod p$ which contradicts $p|(y+kq')$.
If $\bar x$ denote the residue class of $y+kq'$ modulo $q$ and $\bar y$ the residue class of $y$ modulo $q'$, then $\bar x\in U(q)$ and $\bar y=\pi(\bar x)$.
A: We consider three cases:

*

*$′ = ^{\alpha},\, =^{\beta},\quad \alpha\leq\beta,\, \text{ prime}$


*$q' = p_1^{\alpha_1}\ldots p_r^{\alpha_r},\, q' = p_1^{\beta_1}\ldots p_r^{\beta_r},\quad \alpha_i \leq \beta_i,\, p_i \text{ prime}$


*$q' = q_1,\, q = q_1q_2,\quad gcd(q1,q2) = 1$



*

*case 1: Let $a\in\mathbb{Z}$:
$$a + p^{\alpha}\mathbb{Z} \in U\left(p^{\alpha}\right) \iff gcd(a,p^{\alpha}) = 1
\iff gcd(a, p) = 1 \iff gcd(a, p^{\beta}) = 1 \iff a + p^{\beta}\mathbb{Z}\in
U\left(p^{\beta}\right)$$
we have $\pi\left(a+p^{\beta}\mathbb{Z}\right)=a+p^{\alpha}\mathbb{Z}$


*case 2: by chinese remainder theorem:
\begin{align*}
\mathbb{Z}/q'\mathbb{Z} &\simeq \prod_{i=1}^{r}\mathbb{Z}/p_i^{\alpha_i}\mathbb{Z}\\
\mathbb{Z}/q\mathbb{Z} &\simeq \prod_{i=1}^{r}\mathbb{Z}/p_i^{\beta_i}\mathbb{Z}
\end{align*}
so
\begin{align*}
U(q') &\simeq \prod_{i=1}^{r}U(p_i^{\alpha_i})\\
U(q) &\simeq \prod_{i=1}^{r}U(p_i^{\beta_i})
\end{align*}
each $\pi_{i}: U(p_i^{\beta_i}) \to U(p_i^{\alpha_i})$ is surjective so is
$\pi = \pi_{1}\times\ldots\times\pi_{r}$.

*

*case 3:
Let $a\in\mathbb{Z}$ s.t. $a+q_1 \mathbb{Z}\in U(q_1)$. So $gcd(a,q_1) = 1$
The equation $$na -mq_1 = 1,\quad m,n\in\mathbb{Z} \text{ unknown}$$
admits solutions:
\begin{align*}
n &= n_0 + q_1 t\\
m &= m_0 + a t\\
t &\in \mathbb{Z}
\end{align*}
where $n_0, m_0$ are particular solution of the equation.

we want to find a solution to the equation:
$$n'(a - sq_1) - m'q_1q_2 = 1$$
$$n',m', s \in \mathbb{Z} \text{ unknown}$$
the first equation is equivalent to $n' a -q_1(sn' + m'q_2) = 1$
so
\begin{align*}
n' &= n_0 + q_1 t\\
m'q_2 &= m_0 - sn_0 +(a - sq_1)t
\end{align*}
$gcd(q_1,q_2) = 1$ so the mapping
\begin{align*}
\mathbb{Z}/q_2\mathbb{Z} &\to \mathbb{Z}/q_2\mathbb{Z}\\
\bar{s} &\mapsto a -q_1\bar{s}
\end{align*}
is injective, so it is surjective; there exists $s_0\in\mathbb{Z}$ s.t.
$gcd(q_2, a - q_1s_0) = 1$. We put $\alpha = a - q_1s_0,\, \beta = m_0 - s_0 n_0$
By the same argument, the mapping:
\begin{align*}
\mathbb{Z}/q_2\mathbb{Z} &\to \mathbb{Z}/q_2\mathbb{Z}\\
\bar{t} &\mapsto \beta + \alpha\bar{t}
\end{align*}
is surjective, so the equation $m'q_2 = m_0 - sn_0 +(a - sq_1)t$ admits solutions
$m_0^{\prime}, t_0$. Finally we put $n_0^{\prime} = n_0 + q_1 t_0$, so we have
found a particular solution $s_0, n_0^{\prime}, m_0^{\prime}$ to the equation
$$n'(a - sq_1) - m'q_1q_2 = 1$$
we put $b = a -s_0 q_1$; we have $b\in U(q_1q_2)$ and $\pi\left(b+q_1q_2\mathbb{Z}\right) = a + q_1\mathbb{Z}$; so we have proved $\pi$ is surjective.
conceptually we have proved that the three diagrams are commutatives

where $cr_{\star}$ are isomorphisms given by chinese remainder theorem, so
we deduce surjection of the desired homomorphism from the surjectivity of
the others
