# 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?

-
Are you asking what the probability is, or a bound for it, or what it approaches as n gets large? If you're asking what it is, there's only one way to find that out, and that's to compute it for your particular values of x and y, because you need know what the first 3n primes are. (Unless, of course, the answer is a single value for all n.) – John Nov 14 '13 at 20:41
@John A good point. I am after bounds but large $n$ results would be interesting too. – marshall Nov 14 '13 at 20:42
@marshall Just to let you know: I edited my answer with some new things I found. – Eric Thoma Nov 29 '13 at 21:26

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.

To construct $x,y$ such that the probability is high:

1. Multiply together a bunch of small primes. Let that value be $x-c$.
2. 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$.

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$.
Bounds/Asymptotic behaviour of the Chebyshev function should give the probability as asymptotic to $$\frac{\ln 2}{3(\ln m+\ln \ln m-1)}$$ where $m$ is the number of primes. – Ivan Loh Nov 29 '13 at 22:37
Also, I think you misread the question. The OP said that the prime is chosen randomly from the first $3n$ primes, not from the primes $\leq 3n$. (The asymptotic I gave above is for the probability when the prime $p$ is chosen from the first $3n$ primes) – Ivan Loh Nov 29 '13 at 22:45
Your $2/9$ bound is particularly interesting. What do you get if $\lfloor \log_2{x} \rfloor +1 = \lfloor \log_2{y} \rfloor +1$ ? – marshall Nov 30 '13 at 8:26