<s>[INST] If $3$ divides $a^2 + b^2$, then $3$ divides $a$ and $3$ divides $b$ This is a part from a homework. I solved all examples apart from this one. So the task is: We know that $3$ divides $a^2 + b^2$. Prove that $3$ divides $a$ and $3$ divides $b$. I cannot think of anything useful. I know that $a^2 + b^2 = (a + b)^2 - 2ab$, but I don't see how it can help me :(
Best regards,
Petar
 [/INST] Well consider all of the squares modulo 3. $0^2 = 0$, $1^2 = 1$ and $2^2 = 1$. So now take the expression modulo 3, you know that $3 \mid a^2 + b^2$. So $a^2 + b^2 \equiv 0 \pmod 3$, but now if $3$ doesn't divide $a$ or $b$, then $a^2 \equiv 1 \pmod 3$ or $b^2 \equiv 1 \pmod 3$. But that contradicts the assumption that $a^2 + b^2 \equiv 0 \pmod 3$.
</s>