# If $X$ and $Y$ are not divisible by 3, then $X^2 - Y^2$ is divisible by 3

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?

-
x^2 - y^2 = (x + y)(x - y). –  Qiaochu Yuan Oct 17 '10 at 22:43

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.

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

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

-

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

-
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