<s>[INST] 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!
 [/INST] 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$.
</s>