# If $3$ divides $a^2 + b^2$, then $3$ divides $a$ and $3$ divides $b$ [duplicate]

This is a part from a homework. I solved all examples apart from this one. So the task is: We know that $3$ divides $a^2 + b^2$. Prove that $3$ divides $a$ and $3$ divides $b$. I cannot think of anything useful. I know that $a^2 + b^2 = (a + b)^2 - 2ab$, but I don't see how it can help me :(

Best regards, Petar

• Hint: how many solutions does $x^2 = 2$ have mod $3$? Mar 6, 2011 at 16:17
• Use smileys and frowns when you're texting friends; or on chat. Not on MSE's main site, or meta.mse.se. Aug 7, 2017 at 19:37

Well consider all of the squares modulo 3. $0^2 = 0$, $1^2 = 1$ and $2^2 = 1$. So now take the expression modulo 3, you know that $3 \mid a^2 + b^2$. So $a^2 + b^2 \equiv 0 \pmod 3$, but now if $3$ doesn't divide $a$ or $b$, then $a^2 \equiv 1 \pmod 3$ or $b^2 \equiv 1 \pmod 3$. But that contradicts the assumption that $a^2 + b^2 \equiv 0 \pmod 3$.

• I fixed up your LaTeX. To get $a \pmod b$ use a \pmod b Mar 6, 2011 at 16:19
• Thanks, the borwser here doesn't supoort preview... Mar 6, 2011 at 16:25
• Thanks, it seems the task wasn't hard:) (After seeing the solution:P) Mar 6, 2011 at 16:31
• Shouldnt you treat these as cases. If $3$ doesn't divide $a$ but $3$ does divide $b$, $3$ does divide $a$ but $3$ doesn't divide $b$, and lastly, $3$ doesn't divide $a$ and $3$ doesn't divide $b$.
– john
Sep 30, 2019 at 8:14

We know that $a^2+b^2 = 3q$ for $q \in \mathbb{Z}$. Suppose for contradiction that $3$ does not divide $a$ or $3$ does not divide $b$. Then $a = 3l+1$ or $a=3l+2$ and $b = 3l'+1$ or $b=3l'+2$ for $l, l' \in \mathbb{Z}$.

Any integer can be written as one of three forms $3k$, $3k+1$ or $3k+2$.

If we take an integer of the form $3k+1$, then $(3k+1)^2 \equiv 1 (\mbox{mod }3)$. Similarly, if the integer is of the form $3k+2$, then $(3k+2)^2 \equiv 1 (\mbox{mod }3)$. Using these, you can prove your result.

By brute force: $$\rm\: mod\ 3\!:\ 0^2 \equiv 0,\ 1^2 \equiv 2^2\equiv 1\:$$ so $$\rm\: a^2 + b^2 \equiv 1\:$$ or $$\,2\$$ if $$\rm\ a\ or\ b\not\equiv 0$$.
Therefore we conclude that $$\rm\ a^2 + b^2 \equiv 0\ \Rightarrow \ a\ and\ b\equiv 0$$

By theory: if wlog $$\rm\ b\not\equiv 0\$$ then $$\rm\ a^2\equiv -b^2\ \Rightarrow\ (a/b)^2 \equiv -1\$$ contra $$\rm\ x^{2\:}\: \not\equiv -1\ \ (mod\ 3)$$.
This proof works in every field where $$-1$$ is not a square, e.g. integers mod $$\rm\ p = 4n+3\$$ prime, as per the 1st supplement to the law of quadratic reciprocity or, more simply, by Euler's Criterion, as explained at length here. See also here.