5
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ 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. $\endgroup$ – cardboard_box Jan 30 '17 at 23:58
  • 4
    $\begingroup$ 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. $\endgroup$ – positrón0802 Jan 31 '17 at 0:12
  • 1
    $\begingroup$ 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. $\endgroup$ – HighSchool15 Jan 31 '17 at 2:36
  • 1
    $\begingroup$ 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. $\endgroup$ – Winther Jan 31 '17 at 3:09
  • 1
    $\begingroup$ 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. $\endgroup$ – Jonas Meyer Jan 31 '17 at 6:23
4
$\begingroup$

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.

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

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Jonas Meyer Jan 31 '17 at 6:19
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.