Congruences of the form $x^2-a \equiv 0$ (mod pq) Problem: Let p and q be distinct primes. What is the maximum number of possible solutions to a congruence of the form $x^2-a \equiv 0$ (mod pq), where as usual we are only interested in solutions that are distinct modulo pq? (Also provide a proof to support your conjecture.)
Attempt 1: I believe that the answer is p when $p>q$ or q when $q>p$. Am I right or wrong? If I am right can you please help me proof the statement?
I was wrong.
Attempt 2: There are at most 2 solutions because of the Polynomial Roots Mod p Theorem.
 A: The CRT says that if $m$ and $n$ are relatively prime, then the system
$$ \left\{\begin{array}{l}
x \equiv a \pmod m \\
x \equiv b \pmod n
\end{array}\right. $$
has exactly one solution modulo $mn$. As you were told, $x^2 \equiv a \pmod p$ has at most two solutions, and ditto mod $q$. If you have solutions $x_p^2 \equiv a \pmod p$ and $x_q^2 \equiv a \pmod q$, then by the CRT the system
$$ \left\{\begin{array}{l}
x \equiv x_p \pmod p \\
x \equiv x_q \pmod q
\end{array}\right. $$
has exactly one solution mod $pq$, which gives a solution to $x^2 = a \pmod {pq}$. So you will have at most four solutions, since each pair $(x_p,x_q)$ will give a different solution modulo $pq$.
A: Hint $\ $ There are at most two solutions mod $\,p,\,$ because $\,\Bbb Z/p\,$ is a field. Ditto mod $\,q.\, $ By the Chinese Remainder Theorem these can combine to at most $\,\ldots\,$ solutions mod $pq$.
A: You're incorrect. Think about the number of solutions to $x^2\equiv a \mod p$ and $x^2\equiv a \mod q$, then consider the chinese remainder theorem.
