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.


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

| cite | improve this answer | |
  • $\begingroup$ From there, would you use the Chinese Remainder theorem to solve the system of linear congruence to get those four solutions? Thanks, Bill! $\endgroup$ – MathNewbie Jun 28 '12 at 0:03
  • $\begingroup$ @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$ $\endgroup$ – Bill Dubuque Jun 28 '12 at 2:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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