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.

I've been working on proving that there is always a prime between $n$ and $2n$, and also that there is always a prime between $n^2$ and $(n+1)^2$ (Legendre's conjecture).

I believe I've proven those two statements using the following fact:

The most consecutive integers divisible by a number less than or equal to $n$ is $p-2$, where $p$ is the first prime larger than $n$.

For example, if $n=8$ then $p=11$ and I can find at most $9$ consecutive integers divisible by numbers less than $8$. ($200$ through $208$ is one example of consecutive integers divisible by $2,3,5,$ or $7$)

My question is if this fact about consecutive integers divisibility is well known in number theory, or if it is something I will have to prove separately before the other two proofs are valid?

Update: This was proven false in the answer below by Qiaochu Yuan.

share|improve this question
1  
By "the next largest prime above $\,n\,$" , do you mean "the first prime larger than $\,n\,$ ? –  DonAntonio May 1 '13 at 1:53
    
Yes, thank you. I've edited it. –  user1860611 May 1 '13 at 1:55

1 Answer 1

up vote 12 down vote accepted

When checking divisibility by numbers less than or equal to a number it suffices to check primes, so your claim is the following:

Let $p_i$ be the sequence of primes. Then there are at most $p_{i+1} - 2$ consecutive integers each of which is divisible by at least one of the primes $p_1, p_2, ... p_i$.

This claim is false. For example, there are $13 = p_{i+1}$ consecutive integers divisible by at least one of the primes up to $11$ (the claim predicts $11$), namely

$$114, 115, 116, 117, 118, 119, 120, 121, 122, 123, 124, 125, 126.$$

Continuing (at least if my script hasn't made a mistake): there are

  • $21 = p_{i+1} + 4$ consecutive integers divisible by at least one of the primes up to $13$ (ending in $9460$),
  • $33 = p_{i+1} + 10$ consecutive integers divisible by at least one of the primes up to $19$ (ending in $60076$)

and at this point I run out of memory.

The longest string of consecutive integers each of which is divisible by at least one of the numbers $p_1, ... p_i$ is certainly an interesting sequence $q_i$, but a priori we can only expect $q_i \ge p_{i+1} - 2$ (by taking $2, 3, ... p_{i+1} - 1$), and it's not surprising that it was possible to do better.

share|improve this answer

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.