1

How to solve $x^2+y^2 \equiv 8 \pmod 9$?

I know the Chinese Remainder Theorem, but how do I apply it here?

Rodrigo de Azevedo
  • 1
Rhea
  • 87

1 Answers1

2

If we consider each possible residue of $x^2\mod9$, we see that they are

$0^2\equiv 0$

$1^2\equiv 1$

$2^2\equiv 4$

$3^2\equiv 0$

$4^2\equiv 7$

$5^2\equiv 7$

$6^2\equiv 0$

$7^2\equiv 4$

$8^2\equiv 1$

Obviously (in a minor abuse of notation) the solutions have to be $x\in\{4,5\},y\in\{1,8\}$ (or vice versa) (where numbers represent their residue classes) or $x,y\in\{2,7\}$.

auscrypt
  • 8,186
  • The solutions can be $(x,y)=(2,2)$, $(4,8)$, etc. I don't get how the former solution satisfies the conditions you provided. Are there any exceptions? – Rhea Jun 09 '19 at 15:12
  • [x = 4 or 5 mod 9 and y = 1 or 8 mod 9] first solution [y = 4 or 5 mod 9 and x = 1 or 8 mod 9] second solution [x = 4 or 2 mod 7 and y = 2 or 7 mod 9] third solution – auscrypt Jun 09 '19 at 15:15