2
$\begingroup$

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?

  • 12
    x^2 - y^2 = (x + y)(x - y).2010-10-17

3 Answers 3

4

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

  • 0
    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?2010-10-17
  • 0
    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.2010-10-17
  • 0
    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 ....2010-10-17
7

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

6

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.

  • 0
    They can also be in the form of 3k +- 2 and 3t +- 2 right? These come to the same conclusion tho I think?2010-10-17
  • 2
    Yes, it is the same. What happens is that 3k + 2 = 3(k + 1) - 1 and 3k - 2 = 3(k - 1) + 1.2010-10-18