Prove that if $3\mid(a^2+b^2)$,then $3\mid a$ and $ 3\mid b$

Question

I am trying to prove this by contradiction. So if $3$ doesn't divide $a$ or $3$ doesn't divide $b$, then the remainder is either $1$ or $2$. I am struggling on what to do next. How do I get the remainder of $a^2$ and $b^2$ for these cases?

Any help is greatly appreciated. Thank you!

Answer 1

$$(3n+2)^2=3(3n^2+4n+1)+1$$ so both $a^2$and $b^2$ have residue $1$ and their sum residue $2$.

Answer 2

Look the table of addition of $\mathbb{Z}/3$, the square of a number is $0$ or $1$, so $a^2+b^2=0$ implies $a=b=0$.

Answer 3

HINT

Note that

$$a^2+b^2\equiv 0 \pmod 3$$

and since

$$x^2\equiv 0,1 \pmod 3$$

we have that

$$a^2\equiv 0 \pmod 3 \iff a\equiv 0 \pmod 3$$

$$b^2\equiv 0 \pmod 3 \iff b\equiv 0 \pmod 3$$

Answer 4

We have the fact that

If $a \equiv k \mod m$ and $b \equiv l \mod m$ then $ab \equiv kl \mod m$.

So, if $a \equiv 1 \mod 3$ then $a^2 \equiv 1^2 \mod 3$. And if $a \equiv 2 \mod3$ then $a^2 \equiv 2^2\mod3$. And same goes for $b$ as well. Using these, we don't have many cases to consider. Assuming $3|(a^2+b^2)$, we have

• For $a^2 \equiv 1 \mod 3$ and $b^2 \equiv 1 \mod 3$, we have $a^2+b^2 \equiv 2 \mod 3$ which is a contradiction as required.

• For $a^2 \equiv 0 \mod 3$ and $b^2 \equiv 1 \mod 3$ (Checking the "and" condition), we have $a^2+b^2 \equiv 1 \mod 3$ which is a contradiction as required.

Therefore $3 | a$ and $3 | b$.

Answer 5

I am trying to prove this by contradiction.

Why?

A contradiction where the remainder is either 1 or 2 and $a^2$ and $b^2$ can be most combinations ... that's a lot to check.

But a direct proof requires the remainder to be exactly $0$ (one option) which requires $a^2$ and $b^2$ to have opposite (add to a multiple of three) which can only happen one way, is a lot less to check.

.....

Advice: Get use to using negative moduli. Checking remainders being $0$ or $\pm 1$ is a lot easier than checking remainders being $0,1$ or $2$.

Example: If the remainders of $a^2 + b^2=0$, then the remainder of $a^2 = -b^2$ is a lot easier to write then: the remainder of the remainder of $b^2$ is $2$ than the remainder of $a^2$ is $1$ and vice versa, but if one is $0$ they both are.

.......

Taking those in mind the proof practically writes itself!

If $a^2 + b^2 \equiv 0$ then $a^2 \equiv -b^2$. Which means either $a^2 = b^2 =0$ or $a^2 \equiv \pm 1$ which $b^2 \equiv \mp 1$. But $0^2 \equiv 0$ and $(\pm 1)^2 \equiv 1$ so $x^2 \equiv -1$ is impossible. So $a^2 \equiv b^2 \equiv 0$ and $a\equiv b \equiv 0$. i.e. $3$ divides both $a$ and $b$.

Answer 6

Assume $a,b$ are not divisible by $3$. Then: $$a=3m+1 \ \ \text{or} \ \ a=3m+2; \\ b=3n+1 \ \ \text{or} \ \ b=3n+2.$$ Note: $$(3k+1)^2=3(3k^2+2k)+1; \ \ (3k+2)^2=3(3k^2+4k+1)+1.$$ Then: $$a^2+b^2 \equiv 2 \ (\mod 3).$$ Now assume only one of them is divisible by $3$. Then: $$a^2+b^2 \equiv 1 \ (\mod 3).$$ Contradiction, hence both $a$ and $b$ must be divisible by $3$.