# constructive proof of the infinititude of primes

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?

-
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
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
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
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

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.