A very common trap is to think Euclid claims the number 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!
Let us test Euclid's construction on the first few primes. For , (prime); for , (prime); for , (prime); for , (prime); and for , (prime). These first five cases tempt many readers into assuming that is always prime.
However, at the sixth prime , we compute , which is composite because (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 " is either prime or not," and when is composite, its prime factors and are both outside , giving us not just one but two new primes.
- Euclid number
- An integer of the form , 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).