Quadratic residue $a \pmod{pq}$

Question

Let $n = pq$, where $p, q$ are odd prime numbers.

• How prove that the equation $x^2 \equiv a \pmod n$, where $a$ is invertible, $a \in \Bbb Z_n$, either has $4$ different solutions or is not solvable?
• Prove that for irreversible residue $c\ne 0$, $c \in \Bbb Z_n$ satisfying the equation $x^2 \equiv c \pmod n$ has $2$ different solutions?

Any suggestions are welcome! I thought about using Euler's criterion Euler's criterion, but it doesn't really help.

Answer 1

By the Chinese remainder theorem $$ \mathbb{Z}/(n) \cong \mathbb{Z}/(p) \times \mathbb{Z}/(q) $$ where the isomorphism is induced by the map $x \mapsto (x,x)$. This means that finding a solution of $x^2\equiv a$ (mod $n$) is equivalent to finding pairs $(u,v)$ such that $u^2\equiv a$ (mod $p$) and $v^2 \equiv a$ (mod $q$).

I don't want to solve your whole exercise, so think about the following questions

• How many solutions of $x^2\equiv a$ (mod $p$) are there ?
• What do you know about $x$ if $x^2$ is not invertible (mod $n$) ?
• If you have $i$ solutions (mod $p$), and $j$ solutions (mod $q$), then how many solutions do you have (mod $pq$) ?