# Division by 3 proof

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$? –  kahen Mar 6 '11 at 16:17

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 –  kahen Mar 6 '11 at 16:19
Thanks, the borwser here doesn't supoort preview... –  shamovic Mar 6 '11 at 16:25
Thanks, it seems the task wasn't hard:) (After seeing the solution:P) –  Petar Minchev Mar 6 '11 at 16:31

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.

-

$\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 may conclude that $\rm\ a^2 + b^2 \equiv 0\ \ \:\Rightarrow\:\ \ a\ and\ b\equiv 0$

More generally, 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 domain 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.

-