Probability of equality mod p 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?
 A: Issue with this answer
I assumed something that isn't true: that $\left(\prod_{k=1}^{d}p_k\right) + 1> d^d$. This holds for $d>9$, I am fairly sure. I only assumed it for $d>8$, so if you move the bounds I set for $d\ge 8$ to $d>8$ and check $d = 8$ by hand, you will find that my results still work.
Answer
To construct $x,y$ such that the probability is high:


*

*Multiply together a bunch of small primes. Let that value be $x-c$.

*Let y = c.


The resulting pair will have $x \equiv y \bmod{p}$ for every prime (and only those primes) that you chose to multiply together. From the Chinese Remainder theorem, it is clear we can't get "lucky" with a $c$. So $c$ is best just to be $1$ (not $0$ since $y$ must be positive).
Let $x > y$. We can select a set of primes $p_k$ with $k \in K$ and have $x \equiv y \bmod p_k$ for those primes. Then the condition $y \equiv x$ is met for the chosen primes and none others. Thus, from the Chinese Remainder Theorem: $$x \equiv y \mod{\prod_{k\in K}p_k}$$
It does not actually matter the value of $x \bmod{\prod_{k\in K}p_k}$; so long as $y = c$ and $x = \left(\prod_{k\in K}p_k\right) + c$ with $c$ small enough as to not affect $n$. So let $c = 1$. If $c$ were to affect $n$, it could only add more primes into consideration and lower the probability, so we do not lose generality.
Then we are looking for the maximum value of $|{K}|/3n$. $K$ is optimum when it contains all of the primes less than or equal to a value, since adding a large prime to $K$ only serves to raise $n$ more than a small prime. So $K = \{1,2,3,...,d\}$ for some $d$.
Thus, the probability is $d/3n$.
Establishing $1/3$ bound
We know that $x\geq2^d$ since the smallest prime is $2$. So $n\geq d$ from its definition. Then $d/3n \leq n/3n = 1/3$. I believe the strongest bound is $2/9$, occurring when $x=7$ and $y=1$.
Least upper bound: 2/9
We know that $x = \left(\prod_{k=1}^{d}p_k\right) + 1> d^d$. This follows from results here. Then since $n=\lceil{\log_2 x}\rceil$, $$\frac{d}{3n} \leq \frac{d}{3d (\log_2d-1)}=\frac{1}{3(\log_2 d -1)}$$
for $d>2$, where the minus one is to get rid of the ceiling function.
So we can now construct a least upper bound. Observe that for $d\geq8$, the probability is at most $1/6$. We just need to check $d \in \{1,2,3,4,5,6,7\}$ to find $d=2$ gives a maximum value of $2/9 > 1/6$. So the maximum value is $2/9$ at $x = 7$ and $y=1$. I believe a Q.E.D. is in order now.
Continuation: $\lfloor \log_2 x \rfloor = \lfloor \log_2 y \rfloor$
If $\lfloor \log_2 x \rfloor = \lfloor \log_2 y \rfloor$, we have to change our method of choosing $x$ and $y$, since $y \ne 1$.
We will choose $d$ so that $K=\{1,2,\cdots,d\}$ represents the primes $\{2,3,\cdots,p_d\}$ for which $x \equiv y \bmod{p_k}$. The change is that we need to choose $x=c_1 \prod_{k \in K} p_k $ and $y=c_2 \prod_{k \in K} p_k $. If $c1/c2 < 2$ we have a chance that $\lfloor \log_2 x \rfloor = \lfloor \log_2 y \rfloor$. Otherwise it is guaranteed not to hold.
At the same time, we want to minimize $n$. So the most logical choice is $c_1 = 3$ and $c_2 = 2$. Of course there are other possibilities. We will come back to these choices later, but for now it is made an assumption. Now, $x$ and $y$ are chosen and we can proceed as before.
For the purposes of finding the maximum of the probability, we assume $n$ to be as small as possible with choices of $x$ and $y$: $n \ge \log_2 y = \log_2 {\left( 2 \prod_{k \in K} p_k \right)}$. This is not always an integer, but it works for bounds.
We know that $n > \log_2 {2d^d} = 1 + d \log_2 d$, so
$$\frac{d}{3n} < \frac{d}{3(1+d\log_2 d)}$$
For $d \ge 8$, we have that the probability is less than $8/75$ from the previous equation. By testing $d \in \{1,\cdots,7\}$ and throwing out values that do not satisfy $\lfloor \log_2 x \rfloor = \lfloor \log_2 y \rfloor$, we find a maximum probability of $5/39 > 8/75$ at $d=5$, $x=6931$, and $y=4621$  assuming $c_1 = 3$.
Increasing $c_1$ only serves to increase $n$, so the $8/75$ bound for $d \ge 8$ still works. Then increasing $c_1$ can only reduce the probability or leave it be the same. 
The maximum value when $c_1 = 3$ is $1/7$ at $d=3$. We had to throw this one away since $\lfloor \log_2 x \rfloor \ne \lfloor \log_2 y \rfloor$ when $c_1 = 3$. If we choose $c_1 = 4$ and $c_2 = 3$, we achieve the same $1/7$ while satisfying the condition. This is because the small increase in $c_1$ happens to not affect $n$, but brings $x$ and $y$ to be between two consecutive powers of $2$. Now we have our final result:
Satisfying $\lfloor \log_2 x \rfloor = \lfloor \log_2 y \rfloor$, the maximum probability is $1/7$, occurring when $x = 120$ and $y=90$.
Added even later
It has occurred to me that instead of changing $c_2>0$, we could just add a suitably large constant to both $y$ and $x$. I will come back and verify that my result still works in the case where an additive constant is considered. It does appear that one can do better with a modification of the $2/9$ result: add $7$ to both $x=7$ and $y=1$ to get $1/6>1/7$.
