Prove ${a}^{2}+{b}^{2}={c}^{2} \Rightarrow$ 3|ab Prove ${a}^{2}+{b}^{2}={c}^{2} \Rightarrow$ 3|ab
Not sure how to approach this, I considered the contrapositive $3\nmid ab \Rightarrow {a}^{2}+{b}^{2} \neq {c}^{2}$ and then using cases, where case 1 is $ab = 3q+1$ and case 2 is $ab = 3q+2$, but was not able to continue.
Thanks in advance for any help.
 A: There is no square of the form $3k+2$.  $a^2$ and $b^2$ cannot both be of the form $3k+1$, because then $c^2$ would have to be of the form $3k+2$.  Therefore, at least one of $a$ or $b$ has to be a multiple of 3.
A: Using @lulu's hint, we have by Fermat's little theorem that $a^2\cong b^2\cong c^2\cong1\pmod 3$, if $a,b,c\not\cong0\pmod 3$.  But then we get $2\cong1\pmod3\Rightarrow \Leftarrow $.
So, either $a\cong0\pmod3\,,b\cong0\pmod3$, or $c\cong0\pmod 3$.  In the first two cases we're done.   If $c\cong0\pmod 3$, then we get $2\cong0\pmod3\Rightarrow \Leftarrow $ (unless $a\cong0\pmod3$ or $b\cong 0\pmod 3$). 
A: Nothing wrong with just doing things and seeing what happens.
Let $a = 3j + r_1$ and $b= 3k + r_2$ were $r_1 =\pm 1,0$ and $r_2=\pm 1$ or $0$.  If $r_1$ or $r_2=0$ then $3|a$ or $3|b$ and so $3|ab$.  So lets assume $r_1\ne 0$ and $r_2\ne 0$ so $r_1 = \pm 1$ and $r_2 =\pm 1$.
So assume $a = 3j \pm 1$ and $b = 3k \pm 1$ and see if we get a contradiction.
$a^2 + b^2 = c^2$ so $c^2 =9j^2 \pm 6j + 1 + 9k^2 \pm 6k +1= 9(j^2 +k^2) +6(\pm k \pm j) + 2$
Is it possible for a perfect square to have remainder $2$? If $c = 3m$ then $c^2 = 9m^2$ has remainder $0$ and if $c = 3m \pm 1$ then $c^2 =9m^2 \pm 6m + 1$ and has remainder $1$.  So remainder $2$ is impossible.
....
I had no idea.  But .... I figured I'd just do things and see what happened.  .... and it happened.
