# Prove or disprove $p_1p_2\cdots p_n+1$ is prime for all $n\geq 1$

Let $p_1=2$, $p_2=3$, $p_3=5$ and, in general, let $p_i$ be the $i$-th prime. Prove or disprove that

$$p_1p_2 \cdots p_n+1$$

is prime for all $n\geq 1$

Well I was able to find a counter example when $n=6$ but I do not have a general way to show why it shouldn't be prime.

• If you've found a counterexample, you've disproved the statement. There's nothing more to do. However, I'm not sure that n=6 is a counterexample - that's $p_1 p_2 p_6 + 1 = 2 \cdot 3 \cdot 13 + 1 = 79$ which is prime. – cardboard_box Jan 30 '17 at 23:58
• I'm not sure, but I think you meant $p_1p_2\cdots p_n+1$ instead of $p_1p_2p_n+1$. Am I right?. That way you have $p_1p_2\cdots p_6 +1=2\cdot 3 \cdot 5 \cdot 7 \cdot 11 \cdot 13 +1 = 30031$ which is composite. – positrón0802 Jan 31 '17 at 0:12
• Positron0802 you have it correct I fixed it. I understand its not true but was looking for more of a general contradiction type proof to show why its not true. – HighSchool15 Jan 31 '17 at 2:36
• The negation of "for all $n$ the statement $P(n)$ is true" is "there exists a $n$ such that $P(n)$ is false" which is what you have shown. Finding a counter-example (i.e. proving the negation of the statement) like this is the main approach to disproving a false statement. – Winther Jan 31 '17 at 3:09
• Same question on MathOverflow: mathoverflow.net/questions/11398/… Pete L. Clark's answer is about the lack of a known proof (at least, known by the people who weighed in there) that is not done by demonstrating a counterexample. – Jonas Meyer Jan 31 '17 at 6:23

Maybe the best we can do is give an intuition based on the prime number theorem.

If $p_n$ is the $n$th prime, then the prime counting function $\pi(p_n) = n$.

Denote by $p_n\#$ the product of the first $n$ primes. Then, as you already know, $p_n\# + 1$ is not divisible by any of the first $n$ primes. This suggests that it is prime, contradicting, as you already know, the idea that the primes are finite. But if $p_n\# + 1$ is composite, as you already know, it also contradicts the idea that the primes are finite.

If $p_n\# + 1$ is indeed composite, its least prime factor must be greater than $p_n$ but less than $\sqrt{p_n\# + 1}$. Since there are something like $$\frac{\sqrt{p_n\# + 1}}{\log \sqrt{p_n\# + 1}}$$ primes less than $\sqrt{p_n\# + 1}$, there are about $$\frac{\sqrt{p_n\# + 1}}{\log \sqrt{p_n\# + 1}} - n$$ potential least prime factors for $p_n\# + 1$. And since this number is positive and greater than $1$ for $n > 3$, it seems likelier than not that $p_n\# + 1$ does indeed have a nontrivial least prime factor.

• And since $p_n\# + 1 \equiv 3 \bmod 4$, we don't have to worry about this number being a perfect square. Well done. – Robert Soupe Feb 1 '17 at 1:51

"For all" is not the same as "for almost all." The statement you were asked to prove or disprove says "for all $n \geq 1$," not "for all $n \geq 1$ with maybe one or two exceptions."

Then by finding a single $n$ that is a counterexample you have disproven the statement: $$2 \times 3 \times 5 \times 7 \times 11 \times 13 + 1 = 30031 = 59 \times 509.$$ That's it, that's not prime, you've done it.

Keep going a little bit further, though. You'll find that 9699691 is divisible by 347, 223092871 is divisible by 317, 6469693231 is divisible by 331, etc. In fact, take a look at Sloane's A051342: the counterexamples seem to outnumber the examples.

• HighSchool15's comment, "I understand its not true but was looking for more of a general contradiction type proof to show why its not true" seems to indicate that they understand that the counterexample disproves the statement, but wonder whether there is a proof not based on demonstrating a counterexample, for why there must be a counterexample. – Jonas Meyer Jan 31 '17 at 6:19

there's no general way, the $p_1p_2p_3...p_n+1$ expression is usually used to show that there are infinitely many prime numbers.

the number you get by that can be or not be a prime one depending on the situation.