Different ways to prove there are infinitely many primes?

This is just a curiosity. I have come across multiple proofs of the fact that there are infinitely many primes, some of them were quite trivial, but some others were really, really fancy. I'll show you what proofs I have and I'd like to know more because I think it's cool to see that something can be proved in so many different ways.

Proof 1 : Euclid's. If there are finitely many primes then $p_1 p_2 ... p_n + 1$ is coprime to all of these guys. This is the basic idea in most proofs : generate a number coprime to all previous primes.

Proof 2 : Consider the sequence $a_n = 2^{2^n} + 1$. We have that $$ 2^{2^n}-1 = (2^{2^1} - 1) \prod_{m=1}^{n-1} (2^{2^m}+1), $$ so that for $m < n$, $(2^{2^m} + 1, 2^{2^n} + 1) \, | \, (2^{2^n}-1, 2^{2^n} +1) = 1$. Since we have an infinite sequence of numbers coprime in pairs, at least one prime number must divide each one of them and they are all distinct primes, thus giving an infinity of them.

Proof 3 : (Note : I particularly like this one.) Define a topology on $\mathbb Z$ in the following way : a set $\mathscr N$ of integers is said to be open if for every $n \in \mathscr N$ there is an arithmetic progression $\mathscr A$ such that $n \in \mathscr A \subseteq \mathscr N$. This can easily be proven to define a topology on $\mathbb Z$. Note that under this topology arithmetic progressions are open and closed. Supposing there are finitely many primes, notice that this means that the set $$ \mathscr U \,\,\,\, \overset{def}{=} \,\,\, \bigcup_{p} \,\, p \mathbb Z $$ should be open and closed, but by the fundamental theorem of arithmetic, its complement in $\mathbb Z$ is the set $\{ -1, 1 \}$, which is not open, thus giving a contradiction.

Proof 4 : Let $a,b$ be coprime integers and $c > 0$. There exists $x$ such that $(a+bx, c) = 1$. To see this, choose $x$ such that $a+bx \not\equiv 0 \, \mathrm{mod}$ $p_i$ for all primes $p_i$ dividing $c$. If $a \equiv 0 \, \mathrm{mod}$ $p_i$, since $a$ and $b$ are coprime, $b$ has an inverse mod $p_i$, call it $\overline{b}$. Choosing $x \equiv \overline{b} \, \mathrm{mod}$ $p_i$, you are done. If $a \not\equiv 0 \, \mathrm{mod}$ $p_i$, then choosing $x \equiv 0 \, \mathrm{mod}$ $p_i$ works fine. Find $x$ using the Chinese Remainder Theorem.

Now assuming there are finitely many primes, let $c$ be the product of all of them. Our construction generates an integer coprime to $c$, giving a contradiction to the fundamental theorem of arithmetic.

Proof 5 : Dirichlet's theorem on arithmetic progressions (just so that you not bring it up as an example...)

Do you have any other nice proofs?

The following proof is morally due to Euler. We have

$$\prod_{p \text{ prime}} \left( \frac{1}{1 - \frac{1}{p^2}} \right) = \zeta(2) = \frac{\pi^2}{6}.$$

The RHS is irrational, so the LHS must have infinitely many factors.

The following proof is due to Euler. We have

$$\prod_{p \text{ prime}, p \le m} \left( \frac{1}{1 - \frac{1}{p}} \right) \ge \sum_{n=1}^m \frac{1}{n}.$$

The RHS diverges as $m \to \infty$, so the LHS must have an unbounded number of factors.

When I taught undergraduate number theory I subjected my students to a barrage of proofs of the infinitude of the prime numbers: see these lecture notes. I gave eight proofs altogether. Of course by now the list which has been currently compiled has a large overlap with mine, but one proof which has not yet been mentioned is Washington's algebraic number theory proof:

Proposition: Let $R$ be a Dedekind domain with fraction field $K$. If $R$ has only finitely many prime ideals, then for every finite degree field extension $L/K$, the integral closure $S$ of $R$ in $L$ is a PID.

(The proof boils down to two facts: (i) a Dedekind domain with finitely many prime ideals is a PID. (ii) with notation as above, the map $\operatorname{Spec S} \rightarrow \operatorname{Spec R}$ is surjective and at most $[L:K]$-to-one, so $R$ has infinitely many prime ideals iff $S$ has infinitely many prime ideals.)

Corollary: There are infinitely many primes.

Proof: Applying the Proposition with $R = \mathbb{Z}$, if there were only finitely many primes, then for every number field $K$, the ring $\mathbb{Z}_K$ of integers in $K$ would be a PID, hence a UFD. But for instance this fails for $K = \mathbb{Q}(\sqrt{-5})$, as $2 \cdot 3 = (1+\sqrt{-5})(1-\sqrt{-5})$ is a nonunique factorization into ireducible elements (since there are no elements of norm $2$ or $3$) in $\mathbb{Z}_K = \mathbb{Z}[\sqrt{-5}]$.

let $p_1,...,p_n$ be the primes less or equal $N$. any integer less or equal $N$ can be written as $p_1^{e_1}\cdot...\cdot p_n^{e_n}\cdot m^2$ with $e_i\in\{0,1\}$ and $m\leq\sqrt{N}$. so there are at most $2^n\sqrt{N}$ integers less or equal $N$, i.e. $N\leq2^n\sqrt{N}$. simplifying and taking logarithms gives $(1/2)\log N\leq n\log2$. since $N$ is unbounded, so is $n$. (due to erdos taken from the book "gamma" by julian havil, a book on euler's constant)

Proof 3 is due to Fürstenberg (see also the Wikipedia page) and is honestly not that different from Euclid's proof. See this MO question and the corresponding links for an extended discussion.

I give a counting proof here that I think should be better-known. Briefly, let $\pi(n)$ denote the number of primes less than or equal to $n$. The prime factorization of any positive integer less than or equal to $n$ has the form $\prod p_k^{e_k}$ where

$$\sum_{k=1}^{\pi(n)} e_k \log p_k \le \log n$$

so it follows that $e_k \le \log_2 n$ for all $k$, hence that $n \le \left( \log_2 n + 1 \right)^{\pi(n)}$. This gives the following extremely weak version of the PNT:

$$\pi(n) \ge \frac{\log n}{\log (\log_2 n + 1)}.$$

One can use the same idea to prove that any strictly increasing sequence of positive integers which is polynomially bounded has the property that infinitely many primes divide one of its terms, which is stronger than what can be achieved using Euclid's proof (which only gets you this result for polynomials).

Edit: According to Pete Clark's notes, the above proof was in some form given by (but does not seem to be originally due to) Chaitin. In his formulation it can be summarized using the following slogan: if there were finitely many primes, then the prime factorization of a number would be too efficient a way of representing it. This is quite a nice slogan in that it immediately suggests the generalization to polynomially bounded sequences.