<s>[INST] 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$.
 [/INST] 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$
</s>