# Chinese remainder theorem and quadratic congruences

By Chinese remainder theorem there is a solution to $$x \equiv a_{1} \pmod{ p_{1}}, \ ..., \ x \equiv a_{k} \pmod{ p_{k}}$$ if $$p_{1}, \ ..., \ p_{k}$$ are pairwise coprime and $$a_{1}, \ ..., \ a_{k}$$ are integers.

I know that $$x^2 \equiv a \pmod p$$ doesn't always have a solution, however, $$x^2 + y^2 \equiv a \pmod p$$ has a solution $$\forall a \in \mathbb{N}$$.

Therefore I want to prove that there is a solution to $$x^2 + y^2 \equiv a \pmod {p_{i}}, \ ..., \ x^2+y^2 \equiv a \pmod{p_{k}}$$ if $$p_{1}, \ ..., \ p_{k}$$ are pairwise coprime.

One way of proving the Chinese remainder theorem is to find a solution (namely $$x = a_{1}m_{2}p_{2} + a_{2}m_{1}p_{1}$$ where $$m_{2}p_{2}+m_{1}p_{1}=1$$) for the first two congruences and there use induction.

Would it be possible to use a similar proof here?

• Are you assuming $p$ is prime? Because $x^{2} + y^{2} \equiv 7 \bmod{8}$ has no solution. – Morgan Rodgers Apr 24 at 20:17
• Yes, I forgot to mention that. – user663237 Apr 24 at 20:23
• You should incorporate that into your question, that all of your $p_{i}$ are prime. It's important and not clear, since the CRT does not require that. – Morgan Rodgers Apr 24 at 22:00

To find $$x,y\in\mathbb Z$$ with $$x^2+y^2\equiv a_i\pmod{p_i},\quad 1\le i\le k,$$ you can first find $$x_i,y_i\in\mathbb Z$$ satisfying $$x_i^2+y_i^2\equiv a_i\pmod{p_i},\quad 1\le i\le k,$$ and then find $$x,y$$ with $$x\equiv x_i\pmod{p_i}\quad \text{and}\quad y\equiv y_i\pmod{p_i},\quad 1\le i\le k.$$