Probability of equality mod p

Question

Consider two positive integers $x \ne y$ and let $n = max\{\lfloor \log_2{x} \rfloor +1 ,\lfloor \log_2{y} \rfloor +1 \}$. Choose a prime $p$ randomly from the first $3n$ primes. What is the probability that $x \bmod p = y \bmod p$?

I believe it is at most $1/3$. My reasoning is that there are only $n$ primes at most for which $x \bmod p = y \bmod p$. Does this make sense and is there a self contained proof?

I am interested in upper and lower bounds for this probability, especially those that hold for large $n$.

The same question is also at https://math.stackexchange.com/questions/567230/probability-of-equality-mod-p where an upper bound of $2/9$ is now conjectured.

Answer 1

Let $N$ be the number of primes divisors of $|y-x|$ among the $3n$ smallest primes; thus, your probability is $N/(3n)\le \omega(|y-x|)/(3n)$, where $\omega(x)$ is the number of distinct prime divisors of $x$. It is very easy to see, however, that $\omega(x)\le(1+o(1))\log x/\log\log x$. Taking into account that $|y-x|\le\exp(n)$, the probability in question is at most $(1/3+o(1))/\log n=o(1)$; hence, of course, smaller than $2/9$ or any other constant for $n$ sufficiently large.