Prove that if $3|(a^2+b^2)$, then $3|a$ and $3|b$, where $a, b$ are integers I would like to know how to prove the above statement by contradition. Somebody said that one should prove it by this method but I have no idea what it is.
For any integer, there are precisely three options for its reminder when divided by $3$, i.e. $0,1,2$. So suppose that $x_i=3k+i$ for $i=0,1,2$. Then 
$$x_i^2=9k^2+6k+i^2=\begin{cases}3t &amp; i=0\\ 3t+1&amp; i=1,i=2\end{cases}$$
So, for any integer $x$, the reminder of $x^2$ when divided by $3$ is either $0$ or $1$.  Now assume, by the way of contradiction, that $a$ or $b$ are not divisible by $3$. Then what can you say about $a^2+b^2$?
suppose that a=3k+r  , b=3q+r'  r,r'=0,1,2

if a=3k , b=3q its ok

if not r=1,2 a=3k+1 or 3k+2  

so a^2=9k^2+6k+1=3k'+1  ,or 9k^2+12k +4 =3k'+1

and for b like that 

so a^2 mod 3=1 and b^2 mod3 = 1 and it is impossible 

then the only condition that's possible is  a=3k , b=3q 

proof complete