Let $\ a,b,c$ be integers such that $ \ a^{2} + b^{2} = c^{2}$. If $c$ is divisible by $3$, prove that $a$ and $b$ are both divisible by $3$. Question:
Let $\ a,b,c$ be integers such that $ \ a^{2} + b^{2} = c^{2}$. If $c$ is divisible by $3$, prove that $a$ and $b$ are both divisible by $3$. 
My attempt:
Proof by contradiction:
Assume $c$ is divisible by $3$ and $a$ or $b$ is not divisible by $3$. 
Since $c$ is divisible by $3$ we can write $c$ as $ \ c = 3m \implies c^{2} = 9m^{2} \implies 9 | c^{2}$.
Since $a$ and $b$ are not divisible by $3$, $\ a = 3k+1$ and $ \ b = 3n+1$ for some integers $\ k,n.$
Then,
$ a^{2} + b^{2} = (3k+1)^{2} + (3n+1)^{2} = 9k^{2} + 6k +9n^{2} + 6n + 2$.
I am stuck here. I can't find a contradiction. How can I show that $ a^{2} + b^{2} $ is not divisible by $9$.
 A: Assume that the remainders of the divisions $a:3$ and $b:3$ are $r$ and $s$, respectively. Write $a=3p+r$, $b=3q+s$
Then
$$a^2+b^2=9(p^2+q^2)+6(pr+qs)+r^2+s^2$$
Since $r$ and $s$ are $0$, $1$ or $2$, $r^2+s^2$ is $0$, $1$, $4$, $2$, $5$ or $8$. Can you finish?
A: We have $a^2+b^2=c^2\equiv 0\pmod 3$. Since $a^2,b^2\equiv 0$ or $1\pmod 3$ we must to have $a\equiv b\equiv 0\pmod 3$.
A: A couple of points:
1) The negation of "$a$ and $b$ are both divisible by $3$" is "at least one of $a$ or $b$ is not divisible by $3$".
2) You don't need divisibility by $9$ to prove a contradiction. Divisibility by $3$ will do.
A: $$n^2\equiv(0,1,-2,4)mod9.$$ It's all!
A: Note that $(a,b,c)$ is Pythagorean Triples, then we can choose non-zero integers $k;p,q$ and $\gcd (p,q)=1$ such that $$a=2kpq\\b=k(p^2-q^2)\\c=k(p^2+q^2)$$
Now since $3\mid c,$ we will have different cases:
Case 1:
If $3\mid k$, then $3\mid a$ and $3\mid b$
Case 2:
If $3\nmid k$ and $3\mid (p^2+q^2)$. Note that if $3\mid p$, then also $3\mid p$, which can not be true since $\gcd (p,q)=1$. Now since $3\nmid p$ and $3\nmid q$, $3\mid (p^2-q^2)$ (Why?). Then $3\mid b$.
Now since $3\mid c$ and $3\mid b$, then $3\mid (c^2-b^2)\Rightarrow 3\mid a^2\Rightarrow 3\mid a$ (Why?).
But we can not have $3\mid a$ since we have $3\nmid k$, $3\nmid p$, $3\nmid q$.

Hence Case 2 is not possible.


Hence we only have $3\mid k$ which leads to $3\mid a$ and $3\mid b\space\space\space\space\space\blacksquare$
