Prove: if $a$ is a square mod $p,q$, then it is a square mod $pq$

Question

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?

Answer 1

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}$.

Answer 2

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$.