# Let a,b be integers. Then $3 | a^2 + b^2$ if and only if 3 | a and 3 | b [duplicate]

I need to prove this using modular arithmetic but I'm a little stuck. Could I get some pointers? Thank you.

Let $$a,b$$ be integers. Then $$3 | a^2 + b^2$$ if and only if $$3 | a$$ and $$3 | b$$

• Since a square can be only 0 or 1 mod 3 the result follows immediately. – Thomas May 18 at 17:43
• There are only nine combinations of residue classes of $a$ and $b$. You can brute force this soon enough by testing them all. Symmetries will cut it down further very fast also. – Jyrki Lahtonen May 18 at 17:44
• Suppose $3\mid a$ and $3\mid b$. Then that means that... which further means that... implying that $3\mid a^2+b^2$. Now, suppose otherwise that $3\nmid a$ or $3\nmid b$. Without loss of generality, suppose it was that $3\nmid a$. Now, it follows that $a=3k\pm 1$ in which case $a^2=3(3k^2+6k)+1$... Continuing this implies... and further implies... which implies $3\nmid a^2+b^2$ – JMoravitz May 18 at 17:45
• I also warmly recommend that you study our guide for new askers. – Jyrki Lahtonen May 18 at 17:53
• By modular arithmetic there are only three cases of what $a\mod 3$ can be and $3$ cases of what $b \mod 3$ can be so there are only $9$ cases of what $(a^2 + b^2)\mod 3$ can be. If worst comes so worst just do them all and show $(a^2+b^2)\mod 3 \equiv 0 \pmod 3 \iff a\equiv 0 \pmod 3$ and $b\equiv 0 \pmod 3$. But you can reduce this from $9$ steps to a lot fewer be making simple observations for example $x+y= y+x$ so if we test $a\mod 3\equiv x$ and $b\mod 3\equiv y$ we don't need to test $a\mod 3\equiv y$ and $b\mod 3\equiv x$. – fleablood May 18 at 17:59

I'm sure you can show that $$3|a, 3|b \implies 3|a^2+b^2$$ fairly easily. For the other way, note that $$x^2\equiv 1 \pmod 3$$ when $$3$$ doesn't divide $$x$$.
• Congruence notation is $a\equiv b\pmod m$. Meaning that $a-b$ is divisible by $m$. $b$ may be the remainder in integer division of $a$ by $m$, but it isn't constrained to be in the range $[0,m-1]$. OTOH the binary mod is reserved for denoting the remainder: a\bmod m= r yielding $a\bmod m =r$. – Jyrki Lahtonen May 18 at 17:48
• I think you meant "when $3$ doesn't divide $x$", not "when $x$ doesn't divide $3$" – J. W. Tanner May 18 at 17:48