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

-
The question asked you to provide reasoning to support your answer. So...what is the reasoning that supports the answer you have given? – Pete L. Clark Jan 2 '14 at 2:43
Also, the two answers left so far are certainly correct...but I wish they had taken up the challenge of engaging the OP's answer. Both answers give much bigger hints then I would give (at first) to a student who asked me this question. I don't criticize the two answers for their lack of engaging in the socratic method -- the site is set up expressly to encourage more immediate, full answers rather than protracted discussion -- but I do want to remind people that some teaching opportunities are being lost (or at least, very much abridged) here. – Pete L. Clark Jan 2 '14 at 2:50
Have you have looked at some examples? E.g. take $p = 3$, $q = 5$ and $a = 1,2,3,4,5,6$. What do you get? – Pete L. Clark Jan 2 '14 at 2:54
@PeteL.Clark Can you please stop posting rude and offensive remarks? If you do not like my answer and do you think I have put in enough effort then post 1 response acknowledging it. You do not have to harass me and others that are working on this problem. I just wanted to know if I was right or wrong and how to go about the proof of this question. – Username Unknown Jan 2 '14 at 3:00

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