Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
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
up vote 7 down vote accepted

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.


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$.

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$.

share|cite|improve this answer
I would like to know what this graph is asymptotic to. Maybe a prime number theorem application. – Eric Thoma Nov 29 '13 at 21:34
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
@IvanLoh Thanks. Yes I did. I believe that simplifies the problem. I am planning on coming back to work on it in the next couple days. – Eric Thoma Nov 29 '13 at 23:06
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.