# If $3|(a^2 + b^2)$, show that $3|a$ and $3|b$. [duplicate]

I have no idea how to do this problem; please consider helping me:

If $3|(a^2 + b^2)$, show that $3|a$ and $3|b$.

• I found this question. If we look only at the title, then the first one seems like a duplicate. But the current version of that question differs substantial from the original revision, which is the one actually addressed in most answers given there. So it probably would not be wise to mark one of these two question duplicate of the other one. – Martin Sleziak Oct 2 '15 at 13:43
• This question seems very close to this one. – Martin Sleziak Oct 2 '15 at 13:44

The key point is that if $3$ does not divide $x$, then $x^2$ leaves remainder $1$, because $x$ is of the form $3k\pm1$. Therefore:

If $3$ divides $a$ but not $b$ (or vice-versa), then $a^2+b^2$ leaves remainder $1$.

If $3$ divides neither $a$ nor $b$ then $a^2+b^2$ leaves remainder $2$.

So, the only way for $3$ to divide $a^2+b^2$ is for $3$ to divide both numbers.

• Can you explain a little more about that? I don't quite get how to get this conclusion... involve with some certain theory perhaps? – Leon K Oct 2 '15 at 1:02
• Cool I got it now, thx – Leon K Oct 2 '15 at 4:11

From $3\mid a^2+b^2$ we get $a^2\equiv -b^2\pmod 3$. Now assume that $3\nmid a,b$, then because $3$ is prime we get $\gcd(3,a)=\gcd(3,b)=1$. Hence we may divide the first congruence by either $a$ or $b$ (let's do $b$) to get $(a/b)^2\equiv -1\pmod 3$. Hence $-1$ is a quadratic residue mod $3$, contradiction. Thus $3\mid a,b$.

Say $a = 3k_1 + i_1$ and $b = 3k_2 + i_2$, where $0\leq i_1, i_2< 3$. Then we have $$a^2 = (3k_1^2 + i_1)^2 = 9k_1 + 6i_1k_1 + i_1^2 = 3(3k_1^2 + 2 k_1i_1) + i_1^2$$ and similarily, we have $$b^2 = 3(3k_2^2 + 2k_2i_2) + i_2^2$$ Now, each of $i_1$ and $i_2$ are either $0, 1$ or $4$, and you can verify by checking each case that if one or both of them are not $0$, then $i_1^2 + i_2^2$ is not divisible by $3$.

The quadratic residues mod $3$ are $0$ and $1$. The only sum of two of these that is $0$ mod $3$ is $0+0$. Therefore, $a^2\equiv0\pmod3\implies a\equiv0\pmod3$ and $b^2\equiv0\pmod3\implies b\equiv0\pmod3$.