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.

Prove: If $X$ is not divisible by 3 and $Y$ is not divisible by 3, then $X^2 - Y^2$ is divisible by 3.

I cannot find a good way to prove this.. Tried contrapositive and contradiction but cannot see the answer. Anyone have any ideas?

share|improve this question
12  
x^2 - y^2 = (x + y)(x - y). –  Qiaochu Yuan Oct 17 '10 at 22:43
add comment

3 Answers

up vote 6 down vote accepted

If $x$ and $y$ are not divisible by 3 then they must be of the form $x = 3k \pm 1$ and $y = 3t \pm 1$. Therefore $x^2 - y^2 = 9k^2 \pm 6k + 1 -9t^2 \mp 6t -1 = 3(3k^2 - 3t^2 \pm 2k \mp 2t).$ So $x^2 - y^2$ is divisible by 3.

share|improve this answer
    
They can also be in the form of 3k +- 2 and 3t +- 2 right? These come to the same conclusion tho I think? –  Bradley Barrows Oct 17 '10 at 23:24
2  
Yes, it is the same. What happens is that 3k + 2 = 3(k + 1) - 1 and 3k - 2 = 3(k - 1) + 1. –  Adrián Barquero Oct 18 '10 at 0:01
add comment

$x^2-y^2 = (x-y)(x+y)$. If neither $x$ nor $y$ are multiples of $3$, then either they have the same remainder and $x-y$ is a multiple of $3$, or they have different remainders ($1$ and $2$) and $x+y$ is a multiple of $3$.

share|improve this answer
add comment

HINT $\ \ $ mod 3: $\rm\ x\not\equiv 0\ \Rightarrow\ x \equiv \pm 1\ \Rightarrow\ x^2 \equiv 1\:.\ $ Alternatively, without modular arithmetic,

$\quad\quad\quad\ $ 3 divides $\rm\: (x-1)\:x\:(x+1)\ $ but not $\:x\ \Rightarrow\ $ 3 divides $(x-1)(x+1) = x^2 - 1$

Finally, if both $\rm\ x^2-1\ $ and $\rm\ y^2-1\ $ are multiples of 3 then so too is their difference $\rm\ x^2 - y^2$

REMARK $\: $ This proof easily generalizes to show that $\:24\:$ divides $\rm x^2-y^2\:$ if $\rm\:x\:$ and $\rm\:y\:$ are coprime to $6\:$. See here for proof, and for generalizations using Carmichael's function (universal exponent of a group).

share|improve this answer
    
So can I say Y^2 = X^2 mod 3? If so I am still stuck. Sorry. I have been looking at this for hours.. About your answer above, are you saying that is X is not zero then x is congruent to 1 mod 3? –  Bradley Barrows Oct 17 '10 at 23:09
    
He's saying that x is congruent to 1 or 2 mod 3, so x^2 is congruent to 1 or 4 mod 3, and 4 is congruent to 1 mod 3. –  Qiaochu Yuan Oct 17 '10 at 23:13
    
Every integer is congruent, mod 3, to 0, 1, or 2 = -1. Thus if X and Y aren't divisible by 3 they're congruent to 1 or -1, so X^2 and Y^2 are congruent to 1, so X^2 - Y^2 is congruent to .... –  Bill Dubuque Oct 17 '10 at 23:15
add comment

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.