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?
 A: $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$.
A: 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.
A: 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).
