# Prime factors in a range of composite integers

The specific question I am interested in is the following. Let $p_{1}$, $\ldots$, $p_{k}$ be the first $k$ odd primes in succession, and let $n$ be some even integer strictly greater than $p_{k}$. Suppose that $n - p_{i}$ is not prime for any $1 \leq i \leq k$. Experimental evidence suggests that there must then be at least one $i$ with $1 \leq i \leq k$ such that $n - p_{i}$ has a prime factor which is greater than or equal to $p_{k}$. Is there a result in the literature which implies this, or can someone come up with a nice proof?

The consideration of the first $k$ primes here might conceivably be a distraction. What are related known facts about distinct prime factors that can occur in a certain range of composite integers? Grimm's conjecture implies that there are at least $k$ distinct prime factors in a list of consecutive integers of length $k$, but the facts I am looking for seem quite a bit weaker (fortunately, since Grimm's conjecture is expected to be very hard).

Additional comments (01/01/18): to give a little motivation, I will explain that if the above is true for a given $n$ and any $k$, it appears to imply the Goldbach conjecture for $n$. Indeed, suppose that for a fixed $n$ and a given $k$ as above, we have that $n - p_{i}$ is not prime for any $1 \leq i \leq k$. Suppose that we can answer the question I asked in the affirmative, so that there must then be a prime $p'$ greater than or equal to $p_{k}$ which is a prime factor of $n - p_{i}$ for some $i$. Then we can show that the following holds.

Claim. There is a prime which is strictly greater than $p_{k}$ and strictly less than $n$.

Proof of claim. If $p'$ itself is strictly greater than $p_{k}$, then we are done: since $p'$ is a prime factor of $n - p_{i}$, it is certainly strictly less than $n$. If $p'$ is equal to $p_{k}$, then Bertrand's postulate implies that there is a prime $p''$ such that $p' = p_{k} < p'' < 2p_{k}$. Since $n - p_{i}$ is not prime, it has at least one prime factor in addition to (and possibly the same as) $p_{k}$. We thus have that $n - p_{i} \geq 3p_{k}$, so that $p'' < n - p_{i} < n$.

The Goldbach conjecture follows immediately from the claim, by induction. Indeed, since there can be only finitely many primes less than $n$, there must be some integer $k$ to which we cannot apply the claim. For the first such $k$, this means that $n - p_{k}$ is prime, as required.

One might conclude from this that a proof of the question I asked must be very hard. But it doesn't seem that way to me, it seems that quite coarse estimates should be able to do it. I have some ideas, but these seem to be leading in a direction that is a bit more involved than it feels to me should be necessary. I am not an expert on sieve theory or similar things, and I am hoping that somebody who is might see a simple proof or know of a fact from which it follows.

• How about a nice (almost) counterexample? N=30 and k=2. Also, Langevin has a proof for large n. Cf. 262400 . Gerhard "Nice Way To Finish 2017" Paseman, 2017.12.31. – Gerhard Paseman Dec 31 '17 at 16:18
• Why "almost" counterexample? – Aaron Meyerowitz Dec 31 '17 at 16:23
• Because he asks for greater or equal. 25 has a prime factor of 5 which is at least $p_2$. If the poster asked for strictly greater then it would be a counterexample. Gerhard "Just Counting Odd Primes Here" Paseman, 2017.12.31. – Gerhard Paseman Dec 31 '17 at 16:25
• For fixed $k$ there are only finitely many $n$ for which $x=n-3,y=n-5$ are both divisible only by the first $k$ odd primes, since $x/2-y/2=1$ is a solution to the $S$-unit equation, with $S$ being the first $k+1$ primes. Assuming the abc conjecture, you can get a decent upper bound on $n$. – Felipe Voloch Dec 31 '17 at 18:51
• Really? More decent than the lcm of the odd numbers up to (p_k)/2? Gerhard "Prefers One Two Three Theorem" Paseman, 2017.12.31. – Gerhard Paseman Dec 31 '17 at 19:29

## 1 Answer

Oh, let's see a proof sketch variation. (I suspect Erdos originated this bit of folklore, but I know Langevin and Shorey and Tijdeman have published it.)

Let us take n consecutive integers (or in arithmetic progression, with common difference coprime to all). For each integer, consider its largest factor which is a prime power, and map that integer to that prime.

According to the problem, if there is a counterexample, then at least two numbers get mapped to the same prime (regardless of spacing). Then the difference between them must be a prime power less than n (we get to divide out the common difference for free). So one of these at least two Integers must be an odd divisor of lcm(1,...,n).

So if there are any counterexamples for a given n, there are finitely many at most for that n, and are close to a divisor of the least common multiple of the odd numbers that are at most n.

Gerhard "Lets Someone Else Finish Up" Paseman, 2017.12.31.

• Indeed, you can look at n/2 many odd numbers, and show that one of them in a counter example must be even smaller. Gerhard "Even Closer To The Beginning" Paseman, 2017.12.31. – Gerhard Paseman Dec 31 '17 at 18:07