Prove the Ring Homomorphism is Surjective

Solution 1:

Hint: Use the Chinese remainder theorem to show that $f: {Z/pZ} \times {Z/qZ} \to Z/(pqZ)$ is bijective. That's all you should need.

Solution 2:

Yes, one can immediately read off a CRT solution directly from the Bezout identity:

$\quad jp + kq = 1\,\Rightarrow\,\begin{align}{kq\equiv 1\pmod p}\\jp\equiv 1\pmod q\end{align}\,\ $ thus $\,\ x = bjp + akq \ \Rightarrow \begin{align}{x\equiv a\pmod p}\\x\equiv b\pmod q\end{align}$

i.e. $\ {\rm mod}\ (p,q)\!:\,\ \begin{align}kq \equiv (1,0)\\ jp\equiv (0,1)\end{align}\,\Rightarrow\, (a,b) = a(1,0)+b(0,1) \equiv akq + bjp $

which reveals the innate linearity, i.e. how the general solution $\,(a,b)\,$ can be generated as a linear combination of the "basis" solutions $\,(1,0)\,$ and $\,(0,1).\,$ This will become clearer when one studies the ring-theoretic form of CRT (and modules).