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!

  • 1
    $\begingroup$ What precisely do you mean by "same solution"? $\endgroup$ – Bill Dubuque Feb 7 '19 at 3:15
  • $\begingroup$ @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})$. $\endgroup$ – Primavera Feb 7 '19 at 3:22
  • 2
    $\begingroup$ I recommend that you review how CRT works here, e.g. see here. $\endgroup$ – Bill Dubuque Feb 7 '19 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.