Probability approach to divisibility of numbers

Two numbers $x$ and $y$ are chosen at random from the set $\{1,2,3,4,\ldots, 3n\}$. Find the probability that $x^2-y^2$ is divisible by $3$.

I followed following approach $(x-y)(x+y) = 3k$.

It is only when two numbers whose difference is multiple of $3$ is selected viz. $(1,4),(1,7), \ldots, (1,1000)$ etc. or two number whose sum is multiple of $3$ is selected like $(1,2),(1,5)$ etc. From this step, I am not able to proceed as we have case where both are possible e.g $(3,6)$ whose difference and sum is multiple of $3$.

• how many possible values are there of x^2-y^2 ? – user451844 Aug 24 '17 at 11:39

Hint: $x^2-y^2$ is divisible by $3$ if and only if one of the following holds:
• both $x$ and $y$ are multiples of $3$;
• neither $x$ nor $y$ is a multiple of $3$.
We have that $3 | x^2 - y^2 \iff 3 | x-y$ or $3 | x + y$.
Treat the events $E_1 = \{x,y \ |\ 3 \textrm{ divides } x-y \}$ and $E_2 = \{x,y \ |\ 3 \textrm{ divides } x+y \}$. Your desired event $E = \{x,y \ |\ 3 \textrm{ divides } x^2 -y^2 \}$ is the union of these two. So, by the inclusion-exclusion principle: $$P(E) = P(E_1) + P(E_2) - P(E_1 \cap E_2)$$
And you can probably finish from here. To calculate $P(E_1 \cap E_2)$, note that both $x$ and $y$ are multiples of $3$, so you are basically finding the probability that there are multiples of $3$ in both components, which is easy to find.