2
$\begingroup$

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.

1 Answers 1

6

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

  • 0
    @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$2012-06-28