# 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
Correct. there is no expectation it would be. –  ncmathsadist Jul 31 '11 at 2:44
Here is my proof. Suppose there is a finite collection of primes. Let $P$ be its product. Then $P + 1$ is relatively prime to every prime. That is a contradiction, since we know every positive integer splits into a finite product of primes. –  ncmathsadist Jul 31 '11 at 2:59
@Nick: He never said that the product of the first x many primes + 1 would be prime. He's saying the exact same thing as you. –  mixedmath Jul 31 '11 at 3:19