# Is there an infinite number of primes constructed as in Euclid's proof?

In Euclid's proof that there are infinitely many primes, the number $p_1 p_2 ... p_n + 1$ is constructed and proved to be either a prime, or a product of primes greater than $p_n$.

Trivially, we could also use the number $R_n=p_1 p_2 ... p_n - 1$ to prove the theorem, for n>2.

Intuitively, as $n$ grows, the probability that $R_n$ is prime gets smaller. Is there a proof that $R_n$ is not prime for any $n$ greater than some integer $M$ ? Or conversely, that there is an infinite number of prime $R_n$ numbers?

A possibly equivalent question: Is there a prime number greater than $p_n$ and smaller than $R_n$ for any $n$ greater than some integer $M$ ?

-
Perhaps this is pedantry, but this isn't quite what Euclid's proof says. You seem to be using $p_i$ to mean "the $i$th prime", but this doesn't work: after all, if you only know $p_1, \dots, p_n$, then the number $R_n$ won't necessarily give rise to $p_{n+1}$ as a factor. Euclid does something different: he lets $\{p_1, \dots, p_n\}$ be any finite set of primes, then constructs a new one $p_{n+1}$. Here $p_i$ simply means "the $i$th prime that we have found". Your question makes sense in spite of this, but isn't very related to Euclid's proof as it stands. :) –  Billy Jul 31 '11 at 0:57
Euclid did indeed consider arbitrary finite sets of primes, not just the set of the smallest $n$ primes. –  Michael Hardy Jul 31 '11 at 4:30
So I think the answer to the title question is no, the proof isn't really constructive unless you pick all the primes. For example if you just knew that 3 and 5 were primes 3(5)+1=16 which isn't prime or the product of primes greater than ones in your list. –  user9352 Aug 18 '11 at 16:42

The answer to the last question is yes. Much more is known: there is always a prime between $p$ and $2p$, by Bertrand's Postulate, which has long been a theorem.

The numbers $P_n=p_1p_2\cdots p_n +1\:$ have been looked at quite a bit, your $R_n$, for no clear reason, somewhat less. Very little of a general character is known about the $P_n$, and even less about the $R_n$. Prime numbers of either shape are called primorial primes.

It is not known whether there is an infinite number of primorial primes. More startlingly, it is not known whether an infinite number of the $P_n$ or $R_n$ are composite! There has been a great deal of computational work on these numbers, and primes do seem to become scarce among them as $n$ gets large. You can find some information here.

-
For googling purposes, this is called Bertrand's postulate. :) –  Billy Jul 31 '11 at 0:49
I guess you meant $P_n$ to be the one with a '+' ? –  Adrian Jul 31 '11 at 1:12
@Adrian: Thank you, fixed. –  André Nicolas Jul 31 '11 at 1:22

Euclid's proof says that if there were only finitely many primes, the product of these primes +1 would be a new prime. It arrives at a contradiction.

Hence, it really makes no assertion about the product of the first $n$ primes, plus one.

-
Actually, "the product of these primes $+1$" is not asserted to be a new prime; it is merely asserted that this product is divisible by some prime greater than any in the initial collection. –  Nick Strehlke Jul 31 '11 at 1:54
Note the false premise. What I am saying is that were there finitely many primes, their product + 1 must be a new prime. This is a contraction, so no assertion is made there. Only the fact that there is an infinity of primes is revealed. –  ncmathsadist Jul 31 '11 at 2:12
That statement is false though. For instance $2 \cdot 3 \cdot 5 \cdot 7 \cdot 11 \cdot 13 + 1$ is not prime. See the third answer here (third by votes that is): mathoverflow.net/questions/23478/… –  Nick Strehlke Jul 31 '11 at 2:32
@ncm: Your proof in the comments is fine, but the "would be a new prime" in the answer is confusing. I've never seen a version of the proof that contains that assertion. In any case, Euclid's proof doesn't start with the assumption that there are only finitely many primes. –  ShreevatsaR Jul 31 '11 at 4:20
@ncmathsadist: You should not conclude that $P+1$ is relatively prime to every prime, but rather that $P+1$ is relatively prime to every member of the finite collection of primes you started with. –  Michael Hardy Jul 31 '11 at 11:39