Inverse chinese theorem $x \in Qr(n) \iff x \in Qr(p) \wedge x \in Qr( q)$

14 Views Asked by At

I found this sentence in a paper :
Let $n=pq$ where $p, q$ are primes and let $Qr(n) = \{x^2 \mod n | \; x \in Z_n^*\}$ the set of quadratic residues in $Z^*_n$. By Chinese remainder theorem we get :$$x \in Qr(n) \iff x \in Qr(p) \wedge x \in Qr( q)$$
It is not obvious to me why it holds. This is my effort to prove the first direction:
$x \in Q(n) \implies \exists a \in Z_n^*:\; x = a^2 \mod n$
Now I am trying to use something like inverse chinese remainder:
If $x \in Qr(p) \implies \exists b \in Z_p\; : x = b^2 \mod p$
and if $x \in Qr(p) \implies \exists b' \in Z_q\; : x = b'^2 \mod q$
Applying CRT:
$$x = b^2\frac{p}{pq}N_1 + b'^2\frac{q}{pq}N_2$$ where $N_1\frac{1}{q} = 1 \mod p \wedge N_2 \frac{1}{p} = 1\mod q$
I am not sure how to continue.