Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question
    
Hint: how many solutions does $x^2 = 2$ have mod $3$? –  kahen Mar 6 '11 at 16:17
add comment

4 Answers

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|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
add comment

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|improve this answer
add comment

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|improve this answer
add comment

$\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|improve this answer
add comment

Your Answer

 
discard

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.