We have two primes $p,q$ and an integer $a$ such that $$\gcd(a,pq)=1$$
How to prove that for the following congruence $$x^2 \equiv a \mod pq$$
either there will be $4$ solutions or $zero$ solutions.
For example, $p=11,q=7,a=9$. Then the solutions are: $3,74,25,52$
My Approach so far:
Let there exists an integer $k$ such that, $k^2 \equiv a \mod pq$ Assume that there is another solution, say $k+j$ for some integer $j$.
$\implies (k+j)^2 \equiv k^2 \mod pq$
$\implies j(2k+j) \equiv 0 \mod pq$
I need to prove that such $j$ always exists. Moreover, I didn't use the fact that $\gcd(a,pq)=1$.
I'm stuck here. Please help!
If you have solutions, then you have solutions to $x^2 = a \mod p$ and $x^2 = a \mod q$. (Otherwise there are no solutions). Show that there are two solutions to each equation if there exists a solution, and by the Chinese remainder theorem you will then get that there are 4 total solutions $\mod pq$.