Intervals that are free of primes

How can I prove that exists intervals as large as I want that are free of primes?
I mean, $\forall \ k \in \mathbb{N}, \exists \ k$ consecutive positive integers none of which is a prime.

The numbers $6!+2, \ 6!+3, \ 6!+4, \ 6!+5, \ 6!+6$ are five consecutive composite positive integers. Can you generalize that?

By the Chinese remainder theorem you can solve any finite set of congruences of a single unknown modulo pairwise relatively prime numbers. Now to find a sequence of $n$ consecutive non-primes, first fix $n$ pairwise relatively prime numbers $m_1,m_2,\ldots,m_n$ all${}>1$ (which is certainly possible due to the infinite supply of prime numbers), and find a solution $a$ to the congruences \begin{aligned} a&\equiv-1\pmod{m_1},\\ a&\equiv-2\pmod{m_2},\\ a&\equiv-3\pmod{m_3},\\ &\,\vdots \\ a&\equiv-n\pmod{m_n}. \end{aligned} If $a$ should happen to be less than $\max\{m_1,\ldots,m_n\}$, add a multiple of the product $m_1m_2\ldots m_n$ to $a$ to get another solution that satisfies $a\geq\max\{m_1,\ldots,m_n\}$. Now by construction, the number $a+i$ is strictly divisible by $m_i$ for $i=1,\ldots,n$, and therefore composite.

There are proposed some great solutions, but there is also an intuitive solution, which comes from the Chebyshev prime number theorem. The number of prime numbers is $O(log(n))$, so there is always an interval with composite numbers with the length of $O \left(\frac n {log( n)}\right)$ for $n$ which is big enough. Therefore any segment length is reachable.

• If this is an "intuitive solution" for you, then you have a very different sort of intuition than I do. Apr 30 '13 at 17:58
• @Hammerite: This solution says "there aren't enough prime numbers for them to get in the way of finding long intervals of composite numbers".
– user14972
May 1 '13 at 7:47

I would have formulated it another way. Using the contraposit of what we want to prove, there is a k for wich there is no sequence of k consecutive non-prime number. This lead to number of prime at least $\frac{n}{k}$ ie, $O(n)$. This is in contradiction with the prime number theorem suggested by Harold.

• Absolutely the same thing, in fact :) Apr 30 '13 at 12:04

Starting with a simpler problem. It's easy to find a string of four consecutive composite numbers just by checking. But think about how you might go about doing it in a systematic fashion.