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 SS is a finite set of positive prime integers. If SS is empty, then 22 is a positive prime integer not in S.S. Otherwise, let q=1+∏S.q = 1 + \prod S.

Observe that, for any p∈S,p \in S, q≡1(modp).q \equiv 1 \pmod p.

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

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

■\blacksquare