Divisibility of sum of squares

Question

I'm currently working through an olympiad problem book that uses the following fact: $3 \mid a^2 + b^2 \implies 3 \mid a$ and $3 \mid b$.

I don't see how to show this. I know for that a prime $p$ that if $p \mid ab \implies p \mid a$ or $p \mid b$. Could I get a hint?

Answer 1

You can work with congruences modulo $3$. Note that the squares modulo $3$ are $0$ and $1$ ($0^2=0$, $1^2=1$, $2^2=4\equiv 1$). Then $a^2+b^2$ is $0$ if and only if both $a$ and $b$ are $0$ modulo $3$, that is, if both are multiple of $3$.

Another approach is possible working in $\Bbb Z[i]$, that is, the set of complex numbers with integer coordinates. In this set it is true the Fundamental Theorem of Arithmetic and $3$ is a prime in $\Bbb Z[i]$, so you can affirm that $$3|a^2+b^2\Leftrightarrow3|(a+ib)(a-ib)\Leftrightarrow3|a+ib\text{ or }3|a-ib\Leftrightarrow3|a\text{ and }3|b$$

Answer 2

Consider the possible remainders $ x^2mod3$: you only need to try the three classes (squared) $[0]_3,[1]_3 ,[2]_3$