Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question

5 Answers 5

up vote 55 down vote accepted

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

share|improve this answer

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.

share|improve this answer

There are already preferred some great solutions, but there is also the intuitive solution, which comes from the Chebyshev prime number theorem. The number of prime numbers is $O(log(n))$, so there will be 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.

share|improve this answer
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
1  
@Hammerite: This solution says "there aren't enough prime numbers for them to get in the way of finding long intervals of composite numbers". –  Hurkyl May 1 '13 at 7:47

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.

share|improve this answer

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.

share|improve this answer
1  
Absolutely the same thing, in fact :) –  Harold Apr 30 '13 at 12:04

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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