# 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?

• What precisely do you mean by "same solution"? – Bill Dubuque Feb 7 at 3:15
• @BillDubuque If $x\equiv a_{1}\pmod{3}$ and $x\equiv a_{2}\pmod{7}$, same solution means an element of the set $(a_{1}+3\mathbb{Z})\cap(a_{2}+7\mathbb{Z})$. – Primavera Feb 7 at 3:22
• I recommend that you review how CRT works here, e.g. see here. – Bill Dubuque Feb 7 at 3:39

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.

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.