Prove that if $3\mid a^2+b^2$ then $3\mid a$ and $3\mid b$.

The original question was to prove that $c\mid a^2+b^2$ implies $c\mid a$ and $c\mid b$, which as many answers show isn't true.

But this is true if you take the assumption that there isn't a square root of $-1$ mod $c$. Take mod $c$ of the equation to get that

$$a^2 = - b^2 \mod c$$

which can only have a solution $a \neq 0$ or $b \neq 0$ if $-1$ has a square root mod $c$. I.e., there is a number $x$ such that $x^2 = -1 \mod c$.

Indeed, assuming $a$ and $b$ are both relatively prime to $c$, then we can take $b^{-1}$ to get

$$(b^{-1}a)^2 = -1 \mod c.$$

But if no solution exists, our assumption of co-primality cannot hold. If we take the prime factors of $c$ and use modular arithmetic, then we can show $\gcd(a,p) \geq p$ for each prime factor. (Note that $x^2=-1 \mod p$ has a solution if it does mod $c$.) Now this only means $\prod p_i$ divides $a$ and $b$, but if we cancel out these common factors we should be able to repeat the procedure to get full divisibility.

Seeing your edit, the solution follows from my answer by showing mod $3$ that no solution $x^2=-1$ exists. It's a simpler case since $3$ is prime. Sorry I didn't make the above argument tighter, but you should be able to work out the specific (and easier) case from the above.

It's not hard to see the general claim is if and only if as well.

This is not true. Take, for example, $a=3$, $b=4$ and $c=5$.

That's not true. Take $a=3$, $b=4$ and $c=5$.