[Math] Perfect square modulo $n = pq$

cryptographynumber theory

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.

Best Answer

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

Related Question