# Exercise of divisibility of integer numbers

How to prove that if $a$ an $b$ are integers so that $3|(a^2+b^2)$, then $3|ab$?

-
actually, the conclusion is that 3 divides both $a$ and $b$ – Will Jagy Feb 25 '13 at 4:52
@Will Ditto for arbitrary primes - see my answer. – Math Gems Feb 25 '13 at 5:49
Are you familiar with modular arithmetic? – Kasper Feb 25 '13 at 10:57

By cases, depending on the remainder when you divide $a$ (respectively, $b$) by $3$.

-

$\rm mod\ 3\!:\ ab\not\equiv 0\:\Rightarrow\: a,b\not\equiv 0\:\Rightarrow\: a,b\equiv \pm1\:\Rightarrow\: a^2,b^2 \equiv 1\:\Rightarrow\: a^2\!+b^2 \equiv 2\not\equiv 0$

Remark $\,$ More generally: prime $\rm\:p\mid b_1^{p-1}\!\!+\,\cdots+b_n^{p-1}\!\Rightarrow\:p\mid n\ \ or\ \ p\mid b_1,\ldots,p\mid b_n,\:$ since, by little Fermat, $\rm\,mod\ p\!:\ b_i\not\equiv 0\:\Rightarrow\:b_i^{p-1}\!\equiv 1\:\Rightarrow\ 0\equiv b_1^{p-1}\!\!+\,\cdots+b_n^{p-1}\!\equiv n,\:$ i.e. $\rm\:p\mid n.$

-

You could also use the fact the square numbers are either $0 \ \text{mod 3}$ or $1 \ \text{mod 3}$

If you know $3|(a^2+b^2)$ then you can conclude that both $a^2$ and $b^2$ are $0 \ \text{mod 3}$ and so $3$ divides both $a$ and $b$ because $a^2 = 0 \ \text{mod 3}$ implies that $a = 0 \ \text{mod 3}$

-

Examine the possible remainders of a square no. when it is divided by 3.

if a no. is of the form $(3k+1)$ then its square will be $9k^2+6k+1$

if a no. is of the form $(3k+2)$ then its square will be $9k^2+12k+4=9k^2+3(4k+1)+1$

if a no. is of the form $(3k)$ then its square will be $9k^2$

So in each case the remainder can be either $1$ or $0$

Now if the sum of two squares is divisible by 3 it means each of the remainder must be 0 implying each of the no. must be divisible by 3 .Hence $3|ab$

-

$a^2$=0 or 1 (mod 3)

$b^2$=0 or 1 (mod3)

But $a^2+b^2$=0(mod3)

Therefore, each of the squares have to be 0(mod3).

$a^2=0(mod3)<=>$ 3|a

$b^2=0(mod3)<=>$ 3|b

Therefore, 3|ab.

-

Note that if $x\equiv1\pmod3$ then $x^2\equiv1\pmod3$ and if $x\equiv2\pmod3$ then $x^2\equiv1\pmod3$. Thus, if $3\not\mid ab$, then neither $a\equiv0\pmod3$ nor $b\equiv0\pmod3$, therefore, $$3\not\mid ab\Rightarrow a^2+b^2\equiv2\pmod{3}\Rightarrow3\not\mid a^2+b^2\tag{1}$$ Taking the contrapositve of $(1)$ yields $$3\mid a^2+b^2\Rightarrow3\mid ab\tag{2}$$ However, we get even more. From the first implication in $(1)$, if $a^2+b^2\not\equiv2\pmod3$, then $3\mid ab$. That is, $$3\mid (a^2+b^2)(a^2+b^2-1)\Rightarrow3\mid ab\tag{3}$$ which is definitely stronger than $(2)$.

-