0
$\begingroup$

I need to prove this using modular arithmetic but I'm a little stuck. Could I get some pointers? Thank you.

Let $a,b$ be integers. Then $3 | a^2 + b^2$ if and only if $3 | a$ and $3 | b$

$\endgroup$
  • 1
    $\begingroup$ Since a square can be only 0 or 1 mod 3 the result follows immediately. $\endgroup$ – Thomas May 18 at 17:43
  • $\begingroup$ There are only nine combinations of residue classes of $a$ and $b$. You can brute force this soon enough by testing them all. Symmetries will cut it down further very fast also. $\endgroup$ – Jyrki Lahtonen May 18 at 17:44
  • $\begingroup$ Suppose $3\mid a$ and $3\mid b$. Then that means that... which further means that... implying that $3\mid a^2+b^2$. Now, suppose otherwise that $3\nmid a$ or $3\nmid b$. Without loss of generality, suppose it was that $3\nmid a$. Now, it follows that $a=3k\pm 1$ in which case $a^2=3(3k^2+6k)+1$... Continuing this implies... and further implies... which implies $3\nmid a^2+b^2$ $\endgroup$ – JMoravitz May 18 at 17:45
  • $\begingroup$ I also warmly recommend that you study our guide for new askers. $\endgroup$ – Jyrki Lahtonen May 18 at 17:53
  • $\begingroup$ By modular arithmetic there are only three cases of what $a\mod 3$ can be and $3$ cases of what $b \mod 3$ can be so there are only $9$ cases of what $(a^2 + b^2)\mod 3$ can be. If worst comes so worst just do them all and show $(a^2+b^2)\mod 3 \equiv 0 \pmod 3 \iff a\equiv 0 \pmod 3$ and $b\equiv 0 \pmod 3$. But you can reduce this from $9$ steps to a lot fewer be making simple observations for example $x+y= y+x$ so if we test $a\mod 3\equiv x$ and $b\mod 3\equiv y$ we don't need to test $a\mod 3\equiv y$ and $b\mod 3\equiv x$. $\endgroup$ – fleablood May 18 at 17:59
1
$\begingroup$

I'm sure you can show that $3|a, 3|b \implies 3|a^2+b^2$ fairly easily. For the other way, note that $x^2\equiv 1 \pmod 3 $ when $3$ doesn't divide $x$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Congruence notation is $a\equiv b\pmod m$. Meaning that $a-b$ is divisible by $m$. $b$ may be the remainder in integer division of $a$ by $m$, but it isn't constrained to be in the range $[0,m-1]$. OTOH the binary mod is reserved for denoting the remainder: a\bmod m= r yielding $a\bmod m =r$. $\endgroup$ – Jyrki Lahtonen May 18 at 17:48
  • 2
    $\begingroup$ I think you meant "when $3$ doesn't divide $x$", not "when $x$ doesn't divide $3$" $\endgroup$ – J. W. Tanner May 18 at 17:48

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