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.

  • 1
    $\begingroup$ 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. $\endgroup$ – Larry Freeman Mar 11 '16 at 22:25
  • 1
    $\begingroup$ 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. $\endgroup$ – Erick Wong Mar 12 '16 at 0:30
  • $\begingroup$ Fantastic. Thanks very much! :-) $\endgroup$ – 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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