I was trying to understand why if $p=q=3 \pmod 4$ then why each quadratic residue $mod \ {N}$ has a unique square root which itself is a quadratic residue $mod \ N$. Where $N=pq$ and p and q are prime.
This is what I have so far.
By euler's criterion:
$(\frac{-1}{p}) = (-1)^{\frac{4n+3-1}{2}} = (-1)^{2n+1}=-1$
Which mean $-1 \notin \mathbb{QR}_{pq} $
Consider say the root mod $pq$:
$x = x_1c_1+x_2c_2$
and say that it is a square. (Also, $c_1$ and $c_2$ are the Chinese remainder theorem coefficients)
Then for some y:
$x = x_1c_1+x_2c_2 = y^2$
We can then realize that:
$x_1 = y^2 \pmod p$
$x_2 = y^2 \pmod q$
Have to be squares. But $-x_1$ and $-x_2$ are non-squares since the product of a square and a non-square is a non-square (i.e. the product $(-1)(x_1)$ , since from euler's criterion we have -1 is a non-square). This leads me to wonder what about the other three solutions:
$x' = x_1c_1+-x_2c_2$
$x'' = -x_1c_1+x_2c_2$
$x''' = -x_1c_1+-x_2c_2$
Well, I wish I could say that the sum of non-squares leads to non-squares, but I am not sure of that. So I am wondering what happened to these last three solutions? Also, even if they were non-squares, how come the theorem claims that each quadratic residue mod N has a unique square root? Those other 3 solutions seem valid to me even if they are the sums of non-squares. Anyway have an idea what I am missing or were I am wrong?
Thanks in advance!
Also for reference $c_1$ and $c_1$ are Chinese remainder theorem coefficients. i.e.
$c_1 = 1 \pmod p$
$c_1 = 0 \pmod q$
$c_2 = 0 \pmod p$
$c_2 = 1 \pmod q$
Best Answer
The wording in the theorem might be somewhat ambiguous, but the theorem is not claiming that there is a unique square root of a quadratic residue $s$ mod $N$; it is claiming that there is a unique square root of $s$ subject to the condition that it is also a quadratic residue. In other words, it is claiming that exactly one of $x, x', x'', x'''$ is a quadratic residue.
If we assume that $x$ is a quadratic residue, then none of the others can be a quadratic residue mod $pq$ because they are not quadratic residues mod at least one of $p$ or $q$.
For example, for $x' = x_1 c_1 - x_2 c_2$, we have $x' \equiv -x_2$ (mod $q$), and $-x_2$ is not a square mod $q$ since $q \equiv 3$ (mod 4), as you have noted. Therefore $x'$ is not a square mod $q$ and therefore not a square mod $pq$. (Being a square mod $pq$ implies square mod $q$; therefore, not square mod $q$ implies not square mod $pq$.)
Similarly, $x''$ is not a square mod $p$, and $x'''$ is neither a square mod $p$ nor $q$.
This shows that at most one of the square roots can be a quadratic residue; to show that at least one of them is, notice that by changing the signs of $x_1$ and $x_2$ if necessary, we can make $x_1$ into a square mod $p$, and $x_2$ into a square mod $q$; then the corresponding $x$ will be a square mod $pq$ as desired.