4
$\begingroup$

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

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

4 Answers 4

9
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ I fixed up your LaTeX. To get $a \pmod b$ use a \pmod b $\endgroup$
    – kahen
    Mar 6, 2011 at 16:19
  • $\begingroup$ Thanks, the borwser here doesn't supoort preview... $\endgroup$
    – shamovic
    Mar 6, 2011 at 16:25
  • $\begingroup$ Thanks, it seems the task wasn't hard:) (After seeing the solution:P) $\endgroup$ Mar 6, 2011 at 16:31
  • $\begingroup$ 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$. $\endgroup$
    – john
    Sep 30, 2019 at 8:14
4
$\begingroup$

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

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged .