Find a prime before or after some $n$ consecutive composite numbers.

171 Views Asked by At


Goal

I'd like a method to find a prime before or after some $n$ consecutive composites.

One method would be to brute force every prime and check for $n$ consecutive composites before or after it. Another is to check the prime gaps and keep searching until a gap $\ge n$ is found.


Method

For primes $p_{1}<\cdots<p_{n}$, define these congruences

$$x+1\equiv_{p_{1}}0\\\cdots\\x+n\equiv_{p_{n}}0$$

By the Chinese Remainder Theorem (CRT), the solution $x$ is

$x_k = ({p_{1} \cdots p_{n}})k+N$

yielding $n$ consecutive composite numbers

${x+1,\cdots,x+n}$

Then $x+0$ or $x+n+1$ is prime for some $k \in \mathbb{Z}$.


Example

Let primes $p_{1}=3, p_{2}=17$, then by CRT

$x = 51k+32$

When $k=1$, then $x=83$ is prime and occurs before these consecutive composites

$84,85$


Question

Is there a way to show the solution

$x_k = ({p_{1} \cdots p_{n}})k+N$

will always find a prime $x_k$ before or after $n$ consecutive composites?


Answer

As noted in the comments

The arithmetic progression of solutions $x_k = (p_1\cdots p_n) k + N,\, k=1,2,\ldots$ contains infinitely many primes by Dirichlet, since $(p_i,N) = 1$ by $(p_i,x_k)=1.$

This shows there are infinitely many starting primes $x_k$ followed by $n$ composites, infinitely often.