Euclid's number from the primes up to 13

Text

Euclid proves that primes are infinite like this: take some primes, multiply them all, and add $1$. Starting from $2,3,5,7,11,13$, compute $E = 2\cdot 3\cdot 5\cdot 7\cdot 11\cdot 13 + 1,$ check that it is not divisible by any of those primes, and factor it: which new primes appear?

Solution

The product is $2\cdot 3\cdot 5\cdot 7\cdot 11\cdot 13 = 30030$, so $E = 30031$. Divided by each of the six primes, $E$ always leaves remainder $1$: none of them divides it. Factoring gives $E = 30031 = \boxed{59\cdot 509},$ with $59$ and $509$ both prime and new compared to the starting list. This is exactly the heart of Euclid’s argument: the number built always reveals at least one prime not yet listed.