Euclid's proof that there are infinitely many primes

Step 3 of 7: Build N: multiply all listed primes and add 1

In plain words

If you multiply every prime on the list together, you get a big number that every listed prime divides cleanly with zero remainder. By adding just 1 to that product, you deliberately nudge the number off the grid of every prime on the list at the same time.

N = p_1 p_2 \cdots p_n + 1

Detailed analysis

From the finite list $L = \{p_1, p_2, \dots, p_n\}$ , we define the product $P = p_1 p_2 \cdots p_n$ and form the integer $N = P + 1 = p_1 p_2 \cdots p_n + 1$ . Because every prime satisfies $p_i \ge 2$ and the list contains at least one prime, the product satisfies $P \ge 2$ , which guarantees that $N = P + 1 \ge 3 > 1$ .

In Euclid's text (Book IX, Proposition 20), he takes $DE$ to be "the least number measured by $A, B, C$ " (their least common multiple, which for distinct primes equals their product $p_1 p_2 \cdots p_n$ ) and then adds the unit $DF = 1$ to obtain $EF = N$ . Having constructed this specific integer $N > 1$ , we next examine how $N$ behaves when divided by the primes in $L$ .

Terms in this step

Least common multiple: The smallest positive whole number that is a multiple of every number in a given list; for a list of distinct primes, it is simply their product.

Knowledge used in this step

Prime numbers Divisibility, factors and multiples