Congruences of the form $x^2-a \equiv 0$ (mod pq)

Question

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.

Answer 1

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

Answer 2

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.

Answer 3

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