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.
 A: 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 & i=0\\ 3t+1& 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$?
A: Assume without loss of generality $3\not\mid a$. Then $a^{2}\equiv 1\pmod{3}$. Hence, $a^2+b^2\equiv 1\pmod{3}$ or $a^2+b^2\equiv 2\pmod{3}$. In any case, $3\not\mid (a^2+b^2)$. This proves the contrapositive.
A: HINT:
If $3\not|a, a\equiv\pm1\pmod 3\implies a^2\equiv1\pmod 3$
and $a^2\equiv0\pmod 3\iff a\equiv0$
A: 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 
