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.

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

share|improve this question
5  
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
1  
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

2 Answers 2

up vote 19 down vote accepted

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.

share|improve this answer
2  
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.

share|improve this answer
1  
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
1  
@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
1  
@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

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.