Exercise A0.V.2.24

Proposition

There are infinitely many prime integers.

Proof

We will prove that given any finite set of positive prime integers, there exists a prime integer not included in that set.

Suppose $S$ is a finite set of positive prime integers. If $S$ is empty, then $2$ is a positive prime integer not in $S.$ Otherwise, let $q = 1 + \prod S.$

Observe that, for any $p \in S,$ $q \equiv 1 \pmod p.$

Let $U = \{ (i, [q]_i) \mid i \in \mathbb{Z}, 2 \leq i < q \}.$ Suppose $U$ does not contain an element $(i, [0]_i)$ for any $i \in \mathbb{Z}.$ In that case, $q$ is prime, as it has no non-unit proper divisors. Since $q$ is not in $S$, it suffices as a witness.

Suppose otherwise, and let $i$ be the least integer such that $(i,[0]_i) \in U.$ I claim that $i$ is a prime. To see this, suppose $i$ has a proper non-trivial positive factor $j \mid i.$ Then, by transitivity of divisibility, $j \mid q$ which means that $(j,[0]_j) \in U$ and $j < i,$ which contradicts our requirement of minimality. So $i$ is a prime, it is not an element of $S$, and suffices as a witness.

$\blacksquare$