Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I've been stuck on this problem for a while. Any insights to the problem would be great!

We start with $n = pq$, where $p, q$ are distinct odd primes. In addition, $\gcd(a,n) =1$. If $x^2 \equiv a \mod n$ has any solutions, then it has four solutions (where the book does not specify what $a$ is)

So far, we have that $a \equiv x^2 \mod pq$. This implies that $a \equiv x^2 \mod p$ and $a \equiv x^2 \mod q$. I am stuck at this point. So far my thoughts are if $a \equiv x^2 \mod pq$ has a solution, then $a \equiv x^2 \mod p$ and $a \equiv x^2 \mod q$ have solutions (not sure if this is true & if it is true, I couldn't find anything to refer to in my textbook). From here, we can say that $x \equiv \pm c_1 \mod p$ and $x \equiv \pm c_2 \mod q$. This part of my class is dealing with the Chinese Remainder Theorem. Thanks again.

Edit: I added a little more stuff on what I got so far.

share|cite|improve this question
up vote 6 down vote accepted

Hint $\rm\ (\pm x,\pm x)^2 \equiv (a,a)\ mod\ (p,q).\ $ There are $4$ possible sign combinations.

share|cite|improve this answer
From there, would you use the Chinese Remainder theorem to solve the system of linear congruence to get those four solutions? Thanks, Bill! – MathNewbie Jun 28 '12 at 0:03
@MathNewbie Yes, use CRT to lift the solutions mod $\rm(p,q)\:$ to solutions mod $\rm pq.\:$ E.g. mod $15$ the nontrivial sqrts of $1$ are: $\ \ \begin{eqnarray}\rm\ (\ 1,\,-1)\ mod\ (3,5) &\equiv&\rm\ \ \ 4\ mod\ 15^\phantom{M^{M^M}}\\ \rm (\ {-}1,\,1)\ mod\ (3,5) &\equiv&\rm -4 \ mod\ 15_\phantom{M^{M^M}}\qquad\qquad\qquad\qquad\qquad\qquad\qquad\\ \end{eqnarray}$ Note that $\rm\:mod\ p,\ {-}x\not\equiv x,\:$ else $\rm\:p\:|\:2x,\:$ so by $\rm\:p\:$ odd, $\rm\:p\:|\:x\:|\:a,\:$ contra $\rm\:gcd(a,pq) = 1.\qquad$ – Bill Dubuque Jun 28 '12 at 2:52

Your Answer


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.