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

  • $\begingroup$ how many possible values are there of x^2-y^2 ? $\endgroup$ – 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$.

Can you work out the probabilities of each of these options separately?


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.