Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
9  
actually, the conclusion is that 3 divides both $a$ and $b$ –  Will Jagy Feb 25 '13 at 4:52
1  
@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

6 Answers 6

up vote 3 down vote accepted

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

share|improve this answer

$\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.$

share|improve this answer

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}$

share|improve this answer

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$

share|improve this answer

$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.

share|improve this answer

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)$.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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