Proof that $3 \mid \left( a^2+b^2 \right)$ iff $3 \mid \gcd \left( a,b\right)$ After a lot of messing around today I curiously observed that $a^2+b^2$ is only divisible by 3 when both $a$ and $b$ contain factors of 3.  I am trying to prove it without using modular arithmetic (because that would be way too easy), but finding it very difficult to do so.  Is there an easy way to prove this without using modular arithmetic?
I am also interested in a more general statement.  Namely, I want to find the values of $Z$ for which $Z \mid \left( a^2+b^2 \right)$ necessarily implies that $Z \mid \gcd \left( a,b\right)$.  We know that $Z$ cannot be 5, because $3^2+4^2=5^2$.  More generally, if $Z$ is the largest element of a pythagorean triple then the above implication does not hold.

Given that 3 is a factor of A and of B.
If 3 is a factor of A then A is a multiple of 3, say A = 3k, k an integer.Then A²=9k² Analoguously for B² = 9m² So A²+B² = 9k²+9m²=9(k²+m²) and 3 is a factor of 9, k²+m² is another integer.
I think I am seriously overlooking something here? It can't be that easy...
