<s>[INST] Squares modulo a product of distinct odd primes Let $p,q$ be distinct odd primes. Is it true that a number $a$ is a square modulo $pq$ if and only if $a$ is a square modulo $p$ and modulo $q$?
 [/INST] If $x^2\equiv a\pmod{pq}$, then it is immediate that $x^2\equiv a\pmod{p}$ and $x^2\equiv a\pmod{q}$. Thus a square modulo $pq$ is a square modulo each of $p$ and $q$.

Next we prove the converse, if $a$ is a square modulo $p$ and a square modulo $q$, then $a$ is a square modulo $pq$.
So we want to show that if there exist $x, y$ such that $x^2\equiv a\pmod{p}$ and $y^2\equiv a\pmod{q}$, then $a$ is a square modulo $pq$.
By the Chinese Remainder Theorem, there is a $z$ such that $z\equiv x\pmod{p}$ and $z\equiv y\pmod{q}$. 
Then $z^2\equiv x^2\equiv a\pmod{p}$ and $z^2\equiv y^2\equiv a\pmod{q}$. It follows that $z^2\equiv a \pmod{pq}$. 
Remark: Note that we only used the fact that $p$ and $q$ are relatively prime.
</s>