# Prove that for $n \ge 3$, for any integer $w$, $\exists x$ such that $w < x < w + p_n\#$ and lpf$(x) \ge p_{n+3}$

Let $p_n$ be the $n$th prime where $n \ge 3$. Let $p_n\#$ be the primorial for $p_n$ and let lpf$(x)$ be the least prime factor for $x$.

I am feeling like this should be very easy to prove but I am struggling to complete the argument.

This is easy to show if $0 \le w \le p_n$ since from Bertrand's Postulate (see here for example), there exists $u$ such that there are at least 3 primes between $u$ and $2u$. (I can then check each result from $5$ to this $u$).

What is the most straight forward argument to show that this is true for all $w \ge 0$?

One idea I had was to use Bertrand's Postulate to show that $u_1,u_2,u_3$ exist where $1 < u_1 < u_2 < u_3 < 2p_{n}$ where each are relatively prime to each other. Then, show that there exists $v_1,v_2,v_3$ such that $w < v_1, v_2, v_3 < w + p_n\#$ and each $v_i \equiv u_i \pmod {p_n\#}$.

I am not clear how to show that $p_{n+1}$ or $p_{n+2}$ cannot divide any two $v_i, v_j$ where $i \neq j$. If I can show this, then, clearly, there exists $v_i$ where lpf$(v_i) \ge p_{n+3}$

I would appreciate if someone could help me complete this argument.

• Hi Erick, I am interested in both. I wouldn't mind a weaker argument that completes the proof. I am especially interested in a stronger argument so that I can learn a better way to handle the question. – Larry Freeman Mar 11 '16 at 22:25
• I'll convert my previous comment (which had formatting errors) into an addendum to my answer. I deleted it because I thought there was a fundamental calculation error, but actually I think it was fine :P. – Erick Wong Mar 12 '16 at 0:30
• Fantastic. Thanks very much! :-) – Larry Freeman Mar 12 '16 at 1:11

I think your argument can be completed as follows: $v_i$ must be odd, because $u_i$ is odd (I am assuming you are choosing them to be primes > $p_n$). So $v_j - v_i$ is even; if both $v_i$ and $v_j$ are also divisible by $p_{n+1}$ then $v_j-v_i$ is divisible by $2p_{n+1}$. But we can certainly choose $v_1,v_2,v_3$ to lie in an interval of length $2p_n$ somewhere within $[w, w+4p_n]$, so that $|v_j-v_i| < 2p_n$. This precludes $2p_{n+1}$ from dividing $v_j-v_i$ unless $i=j$.

UPDATE: Here is a stronger approach using more analytical methods. The exact number of coprime residues in $\mathbb Z_{p_n\#}$ is $\phi(p_n\#) = \prod_{i=1}^n (p_i-1)$. One of Mertens' theorems gives the asymptotic for the fraction of values this represents in $\mathbb Z_{p_n\#}$:

$$\frac{\phi(p_n\#)}{p_n\#} \sim \frac{e^{-\gamma}}{\log p_n} \sim \frac{e^{-\gamma}}{\log n}.$$

On the other hand, the fraction of values in any interval $[w,w + p_n\#)$ divisible by $p_{n+1}$ is at most $1/p_{n+1} + O(1/p_n\#)$ (there is a tiny error term depending on where $w$ sits modulo $p_{n+1}$). So most of the residues that are coprime to $p_1,\ldots,p_n$ cannot be divisible by $p_{n+1}$.

Likewise, even if we test against $p_{n+1}, p_{n+2}, \ldots, p_{n+\epsilon n}$ the total number of integers divisible by any of these terms will be too small to exceed $\phi(p_n\#)$. More precisely, there exists a constant $n_0$ such that the following holds:

For any $n\ge n_0$ and $w\ge 0$, there is an integer in $[w,w+p_n\#)$ whose least prime factor is at least $p_{n + \lfloor n/2 \rfloor}$.

This follows from the simple fact that $$\sum_{i=1}^{\lfloor n/2 \rfloor} \frac{1}{p_{n+i}} < \frac{n/2}{p_n} \sim \frac{1}{2 \log n},$$

which for large enough $n$ is always less than $e^{-\gamma}/\log n$, together with the fact that the number of terms in the sum is small enough that the tiny error term doesn't make a substantial difference.

We can push the constant $1/2$ a little bit higher as $e^{-\gamma}$ is closer to $0.56$ and the above estimate is lossy, but I suspect there is a more clever sieve-theoretic argument that could do better than this method. To explicitly compute a suitable $n_0$, you can refer to this other answer this cites an effective version of Mertens's theorem by Dusart.