MathLabs
Step 7 of 7: Worked example: why N itself does not have to be prime
In plain words

A very common trap is to think Euclid claims the number N=p1cdotspn+1N = p_1 \\cdots p_n + 1 is always prime. Testing the first few lists shows why that is false: for the first five primes N is prime, but on the sixth prime N = 30031 breaks into 59 × 509 — and both 59 and 509 are still brand-new primes outside our list!

2⋅3⋅5⋅7⋅11⋅13+1=30031=59×5092 \cdot 3 \cdot 5 \cdot 7 \cdot 11 \cdot 13 + 1 = 30031 = 59 \times 509
Detailed analysis

Let us test Euclid's construction on the first few primes. For L={2}L = \{2\}, N=2+1=3N = 2 + 1 = 3 (prime); for L={2,3}L = \{2, 3\}, N=2⋅3+1=7N = 2 \cdot 3 + 1 = 7 (prime); for L={2,3,5}L = \{2, 3, 5\}, N=30+1=31N = 30 + 1 = 31 (prime); for L={2,3,5,7}L = \{2, 3, 5, 7\}, N=210+1=211N = 210 + 1 = 211 (prime); and for L={2,3,5,7,11}L = \{2, 3, 5, 7, 11\}, N=2310+1=2311N = 2310 + 1 = 2311 (prime). These first five cases tempt many readers into assuming that N=p1⋯pn+1N = p_1 \cdots p_n + 1 is always prime.

However, at the sixth prime L={2,3,5,7,11,13}L = \{2, 3, 5, 7, 11, 13\}, we compute N=2⋅3⋅5⋅7⋅11⋅13+1=30030+1=30031N = 2 \cdot 3 \cdot 5 \cdot 7 \cdot 11 \cdot 13 + 1 = 30030 + 1 = 30031, which is composite because 30031=59×50930031 = 59 \times 509 (as emphasized in classic texts such as Hardy and Wright's An Introduction to the Theory of Numbers, §1.2). Notice how Euclid's proof in Book IX, Proposition 20 handles this effortlessly: Euclid explicitly splits into the two cases "EFEF is either prime or not," and when N=30031N = 30031 is composite, its prime factors q=59q = 59 and q=509q = 509 are both outside {2,3,5,7,11,13}\{2, 3, 5, 7, 11, 13\}, giving us not just one but two new primes.

Terms in this step
Euclid number
An integer of the form En=p1p2cdotspn+1E_n = p_1 p_2 \\cdots p_n + 1, equal to 1 more than the product of the first n primes; some Euclid numbers are prime (like 3, 7, 31, 211, 2311) and others are composite (like 30031 = 59 × 509).
Knowledge used in this step
Common mistake. Never write in an exam or proof that N=p1p2⋯pn+1N = p_1 p_2 \cdots p_n + 1 "is therefore a new prime." For instance, 2⋅3⋅5⋅7⋅11⋅13+1=30031=59×5092 \cdot 3 \cdot 5 \cdot 7 \cdot 11 \cdot 13 + 1 = 30031 = 59 \times 509 is composite, and even starting with a non-consecutive list like {3,5}\{3, 5\} gives 3⋅5+1=16=243 \cdot 5 + 1 = 16 = 2^4, whose only prime factor is q=2q = 2. Always say that NN has at least one prime factor qq not in the list.