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.

There are infinitely many prime numbers. Euclides gave a constructive proof as follows.

For any set of prime numbers $\{p_1,\ldots,p_n\}$, the prime factors of $p_1\cdot \ldots \cdot p_n +1$ do not belong to the set $\{p_1,\ldots,p_n\}$.

I'm wondering if the following can be made into a constructive proof too.

Let $p_1 = 2$. Then, for $n\geq 2$, define $p_n$ to be a prime number in the interval $(p_{n-1},p_{n-1} + \delta_n]$, where $\delta_n$ is a real number depending only on $n$. Is such a $\delta_n$ known?

Note that this would be a constructive proof once we find a $\delta_n$ because finding a prime number in $(p_{n-1},p_{n-1}+\delta]$ can be done in finite time algorithmically.

For some reason I believe such a $\delta_n$ is not known. In this spirit, is it known that we can't take $\delta_n = 10n$ for example?

share|improve this question
    
Well, you could define $\delta_n$ to be the difference between the $(n-1)$th and the $n$th prime. This can be constructively shown to exist, by virtue of Euclid's argument. So it doesn't really bring you closer to an independent proof, but it still makes it very difficult to maintain the idea that no working $\delta_n$ is even known. –  Henning Makholm Jun 17 '12 at 22:00
    
This has been answered before: math.stackexchange.com/questions/30127/… (see especially Bill Dubuque's excellent answer) –  Fredrik Meyer Jun 17 '12 at 22:01
3  
By Bertrand's Postulate (which has long been a theorem) there is always a prime between $k$ and $2k$. –  André Nicolas Jun 17 '12 at 22:01
1  
However, what if all known proof of Bertrand's Postulate use the fact that there are infinitely many primes... –  GEdgar Jun 17 '12 at 22:10
1  
Even if the proof used Axiom of Choice, and other mysterious things, it would remain the case that the algorithm that searches from $p_{n-1}+1$ to $2p_{n-1}$ works. –  André Nicolas Jun 17 '12 at 22:14

1 Answer 1

up vote 5 down vote accepted

As noted in the comments, we can take $\delta_n=p_{n-1}$. In fact, there are improvements on that in the literature. But if you want something really easy to prove, you can take $\delta_n$ to be the factorial of $p_{n-1}$, since that gives you an interval which includes Euclid's $p_1\times p_2\times\cdots\times p_{n-1}+1$ and therefore includes a new prime.

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.