Quadratic Residues in mod n

Question

I think that I have a pretty good understanding of how to compute square roots of quadratic residues in $\mathbb Z/p \mathbb Z$ where $p$ is prime. I am wanting to further this understanding in the case of $\mathbb Z/n \mathbb Z$ where $n=pq$ with $p,q$ distinct odd primes.

Some questions I am looking for guidance on include:

• Say $A$ is a quadratic residue. How many solutions does $x^2=A$ have? I believe this answer is 4, but am unsure how to show it.
• How do we find all of these solutions if we know one of them and the factorization of $n$?
• If we had a way to compute all the square roots in $\mathbb Z/n \mathbb Z^*$, how would we be able to factor $n$?

Am I correct in thinking that we will end up using the isomorphism that 'breaks' $\mathbb Z/pq \mathbb Z$ into the two smaller rings $\mathbb Z/p \mathbb Z \times \mathbb Z/q \mathbb Z$? How can we put this to use?

Answer 1

By CRT, $\Bbb Z/(pq\Bbb Z) \cong \Bbb Z/p\Bbb Z \times \Bbb Z/q\Bbb Z$.

If $(a,b) \in \Bbb Z/p\Bbb Z \times \Bbb Z/q\Bbb Z$ is a solution to $x^2 = A$, then so would $(a,-b)$, $(-a,b)$, and $(-a,-b)$. One can also verify that those are the only solutions and there is no overlap (assuming $2 \not\mid pq$).

Therefore, there are $4$ solutions.

Answer 2

If you had square roots $u$ and $v$ of $a$ modulo $pq$, with $u\not\equiv \pm v\pmod{pq}$ then $\gcd(u-v,pq)$ is one of $p$ and $q$.