Prove that if $3\mid(a^2+b^2)$,then $3\mid a$ and $ 3\mid b$ I am trying to prove this by contradiction. So if $3$ doesn't divide $a$ or $3$ doesn't divide $b$, then the remainder is either $1$ or $2$. I am struggling on what to do next. How do I get the remainder of $a^2$ and $b^2$ for these cases?
Any help is greatly appreciated. Thank you!


I am trying to prove this by contradiction.

Why?
A contradiction where the remainder is either 1 or 2 and $a^2$ and $b^2$ can be most combinations ... that's a lot to check.
But a direct proof requires the remainder to be exactly $0$ (one option) which requires $a^2$ and $b^2$ to have opposite (add to a multiple of three) which can only happen one way, is a lot less to check.
.....
Advice:  Get use to using negative moduli.  Checking remainders being $0$ or $\pm 1$ is a lot easier than checking remainders being $0,1$ or $2$.
Example:  If the remainders of $a^2 + b^2=0$, then the remainder of $a^2 = -b^2$ is a lot easier to write then: the remainder of the remainder of $b^2$ is $2$ than the remainder of $a^2$ is $1$ and vice versa, but if one is $0$ they both are.
.......
Taking those in mind the proof practically writes itself!
If $a^2 + b^2 \equiv 0$ then $a^2 \equiv -b^2$. Which means either $a^2 = b^2 =0$ or $a^2 \equiv \pm 1$ which $b^2 \equiv \mp 1$.  But $0^2 \equiv 0$ and $(\pm 1)^2 \equiv 1$ so $x^2 \equiv -1$ is impossible.  So $a^2 \equiv b^2 \equiv 0$ and $a\equiv b \equiv 0$.  i.e. $3$ divides both $a$ and $b$.
