22

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.

P..
  • 14,929
Elmo goya
  • 1,152

5 Answers5

62

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

P..
  • 14,929
12

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.

Marc van Leeuwen
  • 115,048
7

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.

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

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.

Lucas Morin
  • 303
  • 1
  • 10
2

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.