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.
Best Answer
A generalization expressed by a set
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$$
This can be further generalized into a set of unique expressions that define every number or every $x$ and $y$ for a value $k>1$ and $p≥0$$$S={kp,kp+1...kp+(k-2),kp+(k-1)}$$
Using modular arithmetic, we know that $S\equiv \{0,1,2...k-2,k-1\}\pmod k$
Since $x$ and $y$ are any two terms from the set $S$ for any $p≥0$, we know that $x$ and $y$ are really just equal to either any value from $\{0,1,2...k-2,k-1\}$ since we only need to look at the remainder when divided by $k$ to determine divisibility.
Probability using mod
Now we know $x^2-y^2 = (x-y)(x+y)$ meaning either $(x-y)$ or $(x+y)$ have to be divisible by $k$ in order to fulfill the requirement that $x^2-y^2$ is divisible by $k$.
It should be noted that the probability of choosing a random number being expressed by any expression in set $S$ is uniform and is equal to $\frac{1}{k}$. For example, the probability of choosing a number is expressible by $3p+1$ is $\frac{1}{3}$. This can be proved by showing how every number expressed by $kp$ can always be paired with $kp+1,kp+2,...kp+(k-2),kp+(k-1)$, thus showing how there are an equal number of numbers of each type.
Onto the question....
$(x-y)$ is divisible by $k$ if $(x-y)\equiv 0\pmod k$. This simplifies to $(x$ mod $k)-(y \text{ mod}\ k) = 0$. Thus we now need to find the probability that $x$ and $y$ are both expressible by the same expression in the set S.
Now this comes down to a simple problem of asking what is the probability of choosing two of the same elements from the set $S$ without replacement, which is $\frac{k}{k} *\frac{1}{k} =$ $\frac{k}{k^2}$
$(x+y)$ is divisible by $k$ if $(x+y)\equiv 0\pmod k$. This simplifies to $(x$ mod $k)+(y \text{ mod}\ k) = 0$. Thus we now need to find the probability that $x$ and $y$ are chosen such that the $x+y =$ a multiple of $k$.
Knowing that $x$ and $y$ must come from the set $S$, we can see there is a specific pairing of elements from $S$ that causes the addition of the pair of elements to be equal to $2*kp+k$, a multiple of $k$. The only times that the pair of elements, which will be the expression that expresses $x$ and $y$, add up to $2*kp$ is when one is expressed by $kp+m$ and the other being $kp+(k-m)$ for any whole number $m$. This is because $(kp+m)+(kp+(k-m)) = 2*kp$. For example $3p+1$ can be paired up with $3p+2$ since their sum is $6p+3$, a multiple of 3.
Now we are now looking for the probability the two chosen elements from $S$ are pairs of each other (If both chosen elements are $kp$, it will be a multiple of k still) The total number of pairs that can be chosen is the total number of elements in set $S$ squared, which is $k^2$. The total number of pairs that fulfill the divisibility by $k$ is equal to $\lfloor\frac{k}{2}\rfloor + 1$. The ceiling function is applied to correct errors that occur when $k$ is odd as you obviously can't have a fractional number of pairs. The extra $+1$ is for including the case when both elements are the same.
Thus the probability that $(x+y)$ is divisible by $k$ is $\frac{\lfloor\frac{k}{2}\rfloor + 1}{k^2}$.
However now we encounter a problem of overlap, which are the cases when the two elements chosen from $S$ make $(x-y)$ and $(x+y)$ divisible by k. To get rid of the over count we need to subtract the number of times this happens for a given set $S$. We know we need to subtract once for the case when both elements are $kp$. We also need to subtract another one depending if $k$ is even or not. This is because when $k$ is even, we have the case where the element $kp+\frac{k}{2}$ can pair with itself to fulfill everything. Thus the final answer is $$\frac{k}{k^2}+\frac{\lfloor\frac{k}{2}\rfloor + 1}{k^2} - \frac{(k+1 \text{ mod }2)+1}{k^2}$$
The $\frac{(k+1 \text{ mod }2)+1}{k^2}$ tells us to subtract one more and subtract another if $k$ is even, hence we shifted the modular part by 1 since $( \text{ even number mod }2 = 0)$