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!
 A: Look the table of addition of $\mathbb{Z}/3$, the square of a number is $0$ or $1$, so $a^2+b^2=0$ implies $a=b=0$.
A: HINT
Note that
$$a^2+b^2\equiv 0 \pmod 3$$
and since
$$x^2\equiv 0,1 \pmod 3$$
we have that
$$a^2\equiv 0 \pmod 3 \iff a\equiv 0 \pmod 3$$
$$b^2\equiv 0 \pmod 3 \iff b\equiv 0 \pmod 3$$
A: We have the fact that 

If $a \equiv k \mod m$ and $b \equiv l \mod m$ then $ab \equiv kl \mod m$.

So, if $a \equiv 1 \mod 3$ then $a^2 \equiv 1^2 \mod 3$. And if $a \equiv 2 \mod3$ then $a^2 \equiv 2^2\mod3$. And same goes for $b$ as well. Using these, we don't have many cases to consider. Assuming $3|(a^2+b^2)$, we have


*

*For $a^2 \equiv 1 \mod 3$ and $b^2 \equiv 1 \mod 3$, we have $a^2+b^2 \equiv 2 \mod 3$ which is a contradiction as required.

*For $a^2 \equiv 0 \mod 3$ and $b^2 \equiv 1 \mod 3$ (Checking the "and" condition), we have $a^2+b^2 \equiv 1 \mod 3$ which is a contradiction as required.
Therefore $3 | a$ and $3 | b$.
A: $$(3n+2)^2=3(3n^2+4n+1)+1$$ so both $a^2$and $b^2$ have residue $1$ and their sum residue $2$.
A: 
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$.
A: Assume $a,b$ are not divisible by $3$. Then:
$$a=3m+1 \ \ \text{or} \ \ a=3m+2; \\ 
b=3n+1 \ \ \text{or} \ \ b=3n+2.$$
Note:
$$(3k+1)^2=3(3k^2+2k)+1; \ \ (3k+2)^2=3(3k^2+4k+1)+1.$$
Then:
$$a^2+b^2 \equiv 2 \ (\mod 3).$$
Now assume only one of them is divisible by $3$. Then:
$$a^2+b^2 \equiv 1 \ (\mod 3).$$
Contradiction, hence both $a$ and $b$ must be divisible by $3$.
