Arithmetic of integers, divisibility

Question

Show that, for $a$ and $b$ integers, it has been $3|a^{2}+b^{2}$ then $3|a$ and $3|b$.

I tried immediately, assuming that 3 divides the sum, then it has to divide separately.

Answer 1

If $3\nmid a$, then $a$ can be written as $3k\pm1$ and therefore $a^2$ can be written as $3k+1$. The same thing applies to $b$. So:

• if $3\mid a$ and $3\nmid b$, $a^2+b^2\equiv1\pmod 3$;
• if $3\nmid a$ and $3\mid b$, $a^2+b^2\equiv1\pmod 3$;
• if $3\nmid a$ and $3\nmid b$, $a^2+b^2\equiv2\pmod3$.

Answer 2

There are, in general, nine options for $a$ and $b$: $a$ can be on either of the forms $3m, 3m+1, 3m+2$ for some integer $m$, and $b$ can be on either of the forms $3n, 3n+1, 3n+2$ for an integer $n$.

For each of the nine options, check whether $3\mid a^2 + b^2$. For each case where it does, check whether $3\mid a$ and $3\mid b$.

Answer 3

The simple & direct route is to check possible values (all $\bmod 3$) for $n^2 $:

$n\equiv 0 \to n^2\equiv 0 \\ n\equiv 1 \to n^2\equiv 1 \\ n\equiv 2 \to n^2\equiv 1 $

Thus trying the cases for $a^2, b^2\equiv \{0,1\} \bmod 3$ we have $(a^2+b^2)\equiv 0 \bmod 3$ only when $a^2,b^2\equiv 0 $ and thus $a,b\equiv 0 \bmod 3$.

[We can also see that $3 \mid (a^2+b^2+1)$ would mean that $3\nmid a$ and $3\nmid b$.]

---

More interestingly, the opening claim is true in general for every prime $p \equiv 3 \bmod 4$, since $\phi(p) = p{-}1 \equiv 2\bmod 4$ so $\phi(p)/2$ is odd. Then for a primitive root $g$ we know $g^{\phi(p)/2}\equiv -1 \bmod p$ and since only even powers of the primitive roots are quadratic residues, thus $\bf -1$ is not a quadratic residue $\bf \bmod p$.

Then $a^2+b^2\equiv 0\bmod p$, with $a,b\not\equiv 0$, would mean that $a^2\equiv -b^2$ and $(a^{-1}b)^2\equiv -1\bmod p$ which we know is impossible.