= Euclid's theorem
{c}
{wiki}
There are infinitely many <prime numbers>. Indeed, for any finite list of <prime numbers> $p_1,\ldots,p_k$, the <integer> $N=p_1\cdots p_k+1>1$ has a <prime factor>, by the <fundamental theorem of arithmetic>. None of the listed <prime numbers> divides $N$, since each divides $N-1$ and a common <divisor> would divide $1$. Thus no finite list contains all <prime numbers>. The constructed $N$ need not itself be a <prime number>.
For example, the first six <prime numbers> give
$$
2\cdot3\cdot5\cdot7\cdot11\cdot13+1=30031=59\cdot509.
$$
Both <prime factors> lie outside the original list, although $30031$ is a <composite number>. The construction defeats a proposed complete list; it is not a formula guaranteed to produce a <prime number>. Book IX, Proposition 20 of <Euclid's Elements> explicitly considers both possibilities, prime and composite. https://mathcs.clarku.edu/~djoyce/elements/bookIX/propIX20.html[Euclid, Elements, Book IX, Proposition 20: a prime or composite successor]{ref}.
Back to article page
