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?
Best Answer
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}$.