# How do we know Euclid's sequence always generates a new prime? [duplicate]

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.

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

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

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

• 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. – Mario Carneiro Apr 2 '15 at 3:29

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.

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!