# Probability that $x^2-y^2$ is divisible by $k$

Let two numbers $x$ and $y$ be selected from the set of first $n$ natural numbers with replacement(i.e. the two numbers can be same).The question is to find out the probability that $x^2-y^2$ is divisible by $k\in \mathbb{N}$

For $k=2$

Any number can be expressed as $2p,2p+1$.Now $x^2-y^2=(x-y)(x+y)$ If both numbers are of form $2p+1$ then (x-y) would be divisible by $2$ .if two numbers are of different forms then it will not be divisible by $2$.So the probability in this case is $a^2+(1-a)^2$ where $a$ is probability that number chosen is divisible by $2$ which is $\frac{\lfloor \frac{n}{2} \rfloor}{n}$.However this gets complicated with $k=3$ onwards because numbers in different forms may be divisible.In other words if there a generalisation or way to solve for some large $k$.Thanks.

• $k=3$ is actually as easy as $k=2$, since any square is either $3p$ or $3p+1$. Looking at the difference of the two squares, we see that it is divisible by $3$ iff $x$ and $y$ are either both divisible by $3$ or neither of them are. – Arthur Apr 10 '17 at 7:15
• @navinstudent You might be interested in the complete analytic solution of your problem provided in my solution. – Dr. Wolfgang Hintze Apr 13 '17 at 17:12

A good way to generalize this is to use modular arithmetic, or essentially look at the remainder of $\frac{x}{k}$ and $\frac{y}{k}$. As you pointed out in your example for $k=2$, the numbers can only be expressed as $$2*p,2*p+1$$