0
$\begingroup$

Show that, for $a$ and $b$ integers, it has been $3|a^{2}+b^{2}$ then $3|a$ and $3|b$.

I tried immediately, assuming that 3 divides the sum, then it has to divide separately.

$\endgroup$
2
$\begingroup$

If $3\nmid a$, then $a$ can be written as $3k\pm1$ and therefore $a^2$ can be written as $3k+1$. The same thing applies to $b$. So:

  • if $3\mid a$ and $3\nmid b$, $a^2+b^2\equiv1\pmod 3$;
  • if $3\nmid a$ and $3\mid b$, $a^2+b^2\equiv1\pmod 3$;
  • if $3\nmid a$ and $3\nmid b$, $a^2+b^2\equiv2\pmod3$.
| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

There are, in general, nine options for $a$ and $b$: $a$ can be on either of the forms $3m, 3m+1, 3m+2$ for some integer $m$, and $b$ can be on either of the forms $3n, 3n+1, 3n+2$ for an integer $n$.

For each of the nine options, check whether $3\mid a^2 + b^2$. For each case where it does, check whether $3\mid a$ and $3\mid b$.

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

The simple & direct route is to check possible values (all $\bmod 3$) for $n^2 $:

$n\equiv 0 \to n^2\equiv 0 \\ n\equiv 1 \to n^2\equiv 1 \\ n\equiv 2 \to n^2\equiv 1 $

Thus trying the cases for $a^2, b^2\equiv \{0,1\} \bmod 3$ we have $(a^2+b^2)\equiv 0 \bmod 3$ only when $a^2,b^2\equiv 0 $ and thus $a,b\equiv 0 \bmod 3$.

[We can also see that $3 \mid (a^2+b^2+1)$ would mean that $3\nmid a$ and $3\nmid b$.]


More interestingly, the opening claim is true in general for every prime $p \equiv 3 \bmod 4$, since $\phi(p) = p{-}1 \equiv 2\bmod 4$ so $\phi(p)/2$ is odd. Then for a primitive root $g$ we know $g^{\phi(p)/2}\equiv -1 \bmod p$ and since only even powers of the primitive roots are quadratic residues, thus $\bf -1$ is not a quadratic residue $\bf \bmod p$.

Then $a^2+b^2\equiv 0\bmod p$, with $a,b\not\equiv 0$, would mean that $a^2\equiv -b^2$ and $(a^{-1}b)^2\equiv -1\bmod p$ which we know is impossible.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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