21
$\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$
60
$\begingroup$

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

$\endgroup$
11
$\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$
  • 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 '13 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$ – Hurkyl May 1 '13 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
    $\begingroup$ Absolutely the same thing, in fact :) $\endgroup$ – gukoff Apr 30 '13 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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.