1
$\begingroup$

I have no idea how to do this problem; please consider helping me:

If $3|(a^2 + b^2)$, show that $3|a$ and $3|b$.

$\endgroup$
  • 3
    $\begingroup$ I found this question. If we look only at the title, then the first one seems like a duplicate. But the current version of that question differs substantial from the original revision, which is the one actually addressed in most answers given there. So it probably would not be wise to mark one of these two question duplicate of the other one. $\endgroup$ – Martin Sleziak Oct 2 '15 at 13:43
  • 2
    $\begingroup$ This question seems very close to this one. $\endgroup$ – Martin Sleziak Oct 2 '15 at 13:44
6
$\begingroup$

The key point is that if $3$ does not divide $x$, then $x^2$ leaves remainder $1$, because $x$ is of the form $3k\pm1$. Therefore:

If $3$ divides $a$ but not $b$ (or vice-versa), then $a^2+b^2$ leaves remainder $1$.

If $3$ divides neither $a$ nor $b$ then $a^2+b^2$ leaves remainder $2$.

So, the only way for $3$ to divide $a^2+b^2$ is for $3$ to divide both numbers.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Can you explain a little more about that? I don't quite get how to get this conclusion... involve with some certain theory perhaps? $\endgroup$ – Leon K Oct 2 '15 at 1:02
  • $\begingroup$ Cool I got it now, thx $\endgroup$ – Leon K Oct 2 '15 at 4:11
1
$\begingroup$

From $3\mid a^2+b^2$ we get $a^2\equiv -b^2\pmod 3$. Now assume that $3\nmid a,b$, then because $3$ is prime we get $\gcd(3,a)=\gcd(3,b)=1$. Hence we may divide the first congruence by either $a$ or $b$ (let's do $b$) to get $(a/b)^2\equiv -1\pmod 3$. Hence $-1$ is a quadratic residue mod $3$, contradiction. Thus $3\mid a,b$.

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

Say $a = 3k_1 + i_1$ and $b = 3k_2 + i_2$, where $0\leq i_1, i_2< 3$. Then we have $$ a^2 = (3k_1^2 + i_1)^2 = 9k_1 + 6i_1k_1 + i_1^2 = 3(3k_1^2 + 2 k_1i_1) + i_1^2 $$ and similarily, we have $$ b^2 = 3(3k_2^2 + 2k_2i_2) + i_2^2 $$ Now, each of $i_1$ and $i_2$ are either $0, 1$ or $4$, and you can verify by checking each case that if one or both of them are not $0$, then $i_1^2 + i_2^2$ is not divisible by $3$.

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

The quadratic residues mod $3$ are $0$ and $1$. The only sum of two of these that is $0$ mod $3$ is $0+0$. Therefore, $a^2\equiv0\pmod3\implies a\equiv0\pmod3$ and $b^2\equiv0\pmod3\implies b\equiv0\pmod3$.

| cite | improve this answer | |
$\endgroup$

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