Quadratic Residue problem

Question

Suppose I have two primes $p,q$ such that $pq=n$. How can I solve the congruence equation $x^2 \equiv 1 (\mod n)$? Is this done by Chinese Remainder Theorem on $x \equiv 1 (\mod p)$ and $x \equiv 1 (\mod q)$? Help! Do any other alternative approach exist?

Answer 1

$x^2 \equiv 1 (\mod n) \Rightarrow x^2 \equiv 1 (\mod p) \quad$ and $\quad x^2 \equiv 1 (\mod q)$.

So solve $x^2 \equiv 1 (\mod p)$ - say there are $a$ solutions mod $p$. Then solve $x^2 \equiv 1 (\mod q)$ - say there are $b$ solutions mod $q$. Each of the $ab$ pairs from these solutions sets gives you one solution to $x^2 \equiv 1 (\mod n)$ by the Chinese Remainder Theorem.

Unless $p=2$ or $q=2$ you will have $a=b=2$ and so 4 solutions mod $n$.