1
$\begingroup$

This question already has an answer here:

How do we know that $(p_1 \cdot \ldots \cdot p_k)+1$ is always prime, for $p_1 = 2$, $p_2 = 3$, $p_3 = 5$, $\ldots$ (i.e., the first $k$ prime numbers)?

Euclid's proof that there is no maximum prime number seems to assume this is true.

$\endgroup$

marked as duplicate by user21820, Erick Wong, Joel Reyes Noche, Newb, kjetil b halvorsen Apr 8 '15 at 6:22

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • 1
    $\begingroup$ It's not always prime. $\endgroup$ – Jair Taylor Apr 2 '15 at 3:18
  • 2
    $\begingroup$ $$2\cdot 3\cdot 5\cdot 7\cdot 11\cdot 13 + 1 = 30031 = 59\cdot 509$$ $\endgroup$ – Cameron Williams Apr 2 '15 at 3:30
3
$\begingroup$

That's not true. Euclid's proof does not conclude that this expression is a new prime, it concludes that there exists primes that were not in our original list, that lie between the $k'th$ prime and $p_{1}p_{2}...p_{k} + 1$ (including $p_{1}p_{2}...p_{k} + 1$). Among those extra primes that must exist, $p_{1}p_{2}...p_{k} + 1$ may be one of them, or it may not be. It doesn't matter, either way, there are more primes than listed in our initial list.

We have a counter example as soon as $2*3*5*7*11*13 + 1$.

$\endgroup$
  • 2
    $\begingroup$ I would prefer to state this as "Euclid's proof shows that $\prod p_k+1$ has a prime factor not in $p_1,\dots,p_k$", which is true even if you don't assume finitely many primes in the usual "proof by contradiction" approach. $\endgroup$ – Mario Carneiro Apr 2 '15 at 3:29
3
$\begingroup$

Euclid's proof does not deduce that $\,N = 1+p_1\cdots p_k\,$ is prime. Rather, Euclid's proof deduces that $\,N\,$ is coprime to all $\,p_i,\,$ so the prime factors of $\,N\,$ cannot include any $\,p_i.\,$ But since $\,N> 1\,$ it has some prime factor $\,p\,$ (e.g. its least factor $> 1),\,$ which yields a prime $p$ distinct from all $\,p_i$

The key idea is not that Euclid's sequence $\ f_1 = 2,\,\ \color{#0a0}{f_{n}} = \,\color{#c00}{\bf 1} + f_1\cdots f_{n-1}$ is an infinite sequence of primes but, rather, that it is an infinite sequence of coprimes, i.e. $\,{\rm gcd}(f_n,f_k) = 1\,$ when $\,n>k,\,$ since then any common divisor of $\,\color{#0a0}{f_n},\,\color{#b0f}{f_k}\,$ must divide $\ \color{#c00}{\bf 1} = \color{#0a0}{f_n} - f_1\cdots \color{#b0f}{f_k}\cdots f_{n-1}.$

Any infinite sequence $\,f_n > 1 \,$ of coprimes yields an infinite sequence of distinct primes $\, p_n $ obtained by choosing $\,p_n$ to be any prime factor of $\,f_n,\,$ e.g. the least prime factor.

Remark $\ $ This misunderstanding often arises from reading a proof of Euclid's result reformulated to be by contradiction (which was not used by Euclid). In one form, it can be deduced that if there are only finitely many primes $\,p_1,\ldots p_k,\,$ then $\,n = 1+p_1\cdots p_k\,$ is prime, because $\,n > 1\,$ has no smaller prime factors. But this does not imply that $\,n\,$ is actually prime because the deduction depends on the hypothesis that there are only finitely many primes, which is false in the (actual) natural numbers $\,\Bbb N.\,$ Because the proof by contradiction is carried out in the hypothetical universe "$\Bbb N$ with finitely many primes", one cannot apply any of its conclusions to the (actual) universe $\Bbb N.\,$ It is the nature of proofs by contradiction that one can deduce all sorts of nonintuitive results. When this occurs in a universe like $\,\Bbb N\,$ where we have very strong intuition, it can be quite challenging to keep things straight.

$\endgroup$
0
$\begingroup$

As others have mentioned, the proof you are referring to is probably the proof by contradiction that there are infinitely many primes. Compare with the following statement:

If there are finitely many non-square numbers, then there is a largest non-square number $n$ and so $n+2$ is a square.

One can see that the above statement is true, but that certainly does not imply that if we start with any non-square number $x$, we would get $x+2$ to be a square number!

$\endgroup$

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