Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
4  
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 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 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 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 at 3:00
2  
I'm sorry to hear that you found my comments "rude and offensive". Also, what I lamented about in my second commment has happened more fully: a third person came along and left a complete answer which doesn't ask or address what you tried to do to solve the problem. So now you have a complete answer to the question...but the wording of your question implies that this is not something that you need the answer to in your own work but rather a question that is designed to help you make and test conjectures and eventually prove them. I worry that you got a bit shortchanged... –  Pete L. Clark Jan 2 at 6:22
add comment

3 Answers 3

up vote 4 down vote accepted

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

share|improve this answer
add comment

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.

share|improve this answer
add comment

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

share|improve this answer
    
Ok, I overlooked the Polynomial Roots Mod p Theorem. Can you explain the procedure of using the Chinese Remainder, since the book I am using has not cover that material yet –  Username Unknown Jan 2 at 2:49
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.