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!
Best Answer
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.