22
$\begingroup$

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.

$\endgroup$

5 Answers 5

62
$\begingroup$

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

$\endgroup$
12
$\begingroup$

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.

$\endgroup$
7
$\begingroup$

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.

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

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.

$\endgroup$
1
  • 1
    $\begingroup$ Absolutely the same thing, in fact :) $\endgroup$
    – gukoff
    Apr 30, 2013 at 12:04
2
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .