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?

  • 2
    $\begingroup$ Are you assuming $p$ is prime? Because $x^{2} + y^{2} \equiv 7 \bmod{8}$ has no solution. $\endgroup$ – Morgan Rodgers Apr 24 at 20:17
  • $\begingroup$ Yes, I forgot to mention that. $\endgroup$ – user663237 Apr 24 at 20:23
  • 1
    $\begingroup$ 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. $\endgroup$ – 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. $$

  • $\begingroup$ Thank you so much. $\endgroup$ – user663237 Apr 24 at 20:37

Your Answer

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