Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
Hint: how many solutions does $x^2 = 2$ have mod $3$? – kahen Mar 6 '11 at 16:17
up vote 7 down vote accepted

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$.

share|cite|improve this answer
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}$.

share|cite|improve this answer

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.

share|cite|improve this answer

$\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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.