Solution to a system of quadratic congruences. The following is a system of quadratic congruences:
$$\left\{\begin{array}{cl}x^{2}\equiv a&\pmod{3}\\x^{2}\equiv b&\pmod{7}\end{array}\right.$$
If $\left(\frac{a}{3}\right)=1=\left(\frac{b}{7}\right)$, where $(\ast)$ is the Legendre symbol, then above system has four solutions by the Chinese remainder theorem.
But, I'm wondering about that: Is it possible the first and second congruence has the same solution?
Since $\gcd(3,7)=1$, I guess it is impossible, but I can't explain clearly.
How do I explain it?
Give some advice. Thank you!
 A: Let $x$ be any solution to $x^2\equiv a\pmod{3}$ and $y$ any solution to $y^2\equiv b\pmod{7}$. Then $x+3m$ is also a solution for any integer $m$, and $y+7n$ is also a solution for any integer $n$. So it suffices to show that there exist integers $m$ and $n$ such that
$$x+3m=y+7n,$$
or equivalently $3m+7(-n)=y-x$. Such $m$ and $n$ exist because $3$ and $7$ are coprime. Concretely, as
$$3\times(-2)+7\times(1)=1,$$
we can take $m=-2(y-x)$ and $n=-1(y-x)$ to find that
$$x-6(y-x)=y-7(y-x)=7x-6y,$$
satisfies both congruences simultaneously.
A: Let's assume that $\gcd(n,m)=1$ and that we have integers $\alpha,\beta \in \mathbb Z$ each solving one of the quadratic congruences such that
$$\alpha^2 \equiv a \pmod n \quad \land \quad \beta^2 \equiv b \pmod m$$
Then, using the CRT twice, we can be sure that there exist $y, z \in \mathbb Z$ satisfying 
$$
\begin{align}
& y \equiv \alpha \pmod n \quad \land \quad y \equiv 1 \pmod m\\
\text{and also } & z \equiv 1 \pmod n \quad \land \quad z \equiv \beta \pmod m
\end{align}
$$
For the product $x:=yz$, it follows that
$$
\begin{align}
&x^2 \equiv y^2z^2 \equiv \alpha^21^2 \equiv a \pmod n\\
\text{and also } & x^2 \equiv y^2z^2 \equiv 1^2\beta^2 \equiv b \pmod m
\end{align}
$$
So, if both quadratic congruences are solvable individually and $\gcd(n,m)=1$, then both quadratic congruences are also solvable simultaneously.
