Prove: if $a$ is a square mod $p,q$, then it is a square mod $pq$ For distinct odd primes $p,q$, if $x^2\equiv a \pmod {\! p}$ is solvable and $x^2\equiv a \pmod {\!q}$ is solvable, then $x^2\equiv a \pmod {\! pq}$ is solvable.
Here, I am also assuming neither $p$ nor $q$ divides $a$.
Some students in my Elementary Number Theory class are suggesting that this is directly implied by the Chinese remainder theorem (CRT).  I do not agree because I think CRT says that there is a congruence class (which we can represent by an integer, $x$, in $\{1,2,...,pq-1\}$) in which $x\equiv a \pmod {\! pq}$.  The CRT does not say that this solution is a square (a quadratic residue) mod $pq$.  Right?     
 A: Let $ c $ be  a solution of the congruence $x^2\equiv a\pmod{p}$, and let $ d $ be a solution of $ y^2 \equiv a \pmod{q}$.
By the Chinese Remainder Theorem, the system $ z \equiv c\pmod{p}$, $ z \equiv d \pmod{q} $ has a solution if p and q are coprime.
If $ z $ is a solution of the system, then $ z^2 \equiv c^2 \equiv a \pmod{p}$ and $z^2 \equiv d^2 = a \pmod{q} $. It follows that $ z^2 \equiv a \pmod{pq}$.
A: By CRT we can lift roots mod $\,p,q\,$ to a  root mod $\,pq,\,$ for any polynomial $\,f\in\Bbb Z[x]$ 
Suppose that $\ f(x_p)\equiv 0\pmod p\ $ and $\ f(x_q)\equiv 0\pmod q$
By CRT there is an $\,x\equiv x_p\pmod p,\,\ x\equiv x_q\pmod q$
${\rm Thus}\quad\  {\rm mod}\ p\!:\,\ x\equiv x_p\,\Rightarrow f(x)\equiv f(x_p)\equiv 0$
${\rm and}\quad\ \ \ {\rm mod}\ q\!:\,\ x\equiv x_q\,\Rightarrow f(x)\equiv f(x_q)\equiv 0\,\ $ by the Polynomial Congruence Rule.
So $\,\ p,q\mid f(x)\,\Rightarrow\, {\rm lcm}(p,q) = pq\mid f(x),\ $ i.e. $\ f(x)\equiv 0\pmod{pq}$
The OP is the special case $\, f(x) = x^2-a$.
