Prove that there are infinitely many primes

Let $p_1,\dots ,p_k$ be any finite list of primes, and put
$$N=p_1{p}_2\cdots p_k+1.$$

$N>1$, so it has a prime divisor $q$. If $q$ were one of the $p_i$, then $q$ would divide both $N$ and the product $p_1\cdots p_k$, and so would divide their difference, which is $1$. Impossible. So $q$ is a prime outside the list.

No finite list contains every prime. Hence there are infinitely many.

Two things almost everyone gets wrong about this

It is not a proof by contradiction, although it is nearly always taught as one. Euclid never assumes the primes are finite. He takes any finite list and produces a prime not on it — a construction, not a refutation. The contradiction framing is a later accretion, and it makes a perfectly constructive argument look like a negative one.

$N$ itself need not be prime. A common misreading. For instance
$$2\cdot 3\cdot 5\cdot 7\cdot 11\cdot 13+1=30031=59\times 509.$$
The proof never claims $N$ is prime; it needs only that $N$ has some prime factor.

Cost: every integer greater than $1$ has a prime divisor. That is the whole bill.

Let $F_n=2^{2^n}+1$. The identity
$$F_0{F}_1\cdots F_{n-1}=F_n-2$$
is a one-line induction. For $n=1$ it reads $3=5-2$. Multiplying both sides by $F_n$,
$$F_0\cdots F_n=(F_n-2)F_n={\left(2^{2^n}\right)}^2-1=2^{2^{n+1}}-1=F_{n+1}-2.$$

Now suppose some prime $q$ divides both $F_m$ and $F_n$, with $m<n$. Then $q$ divides the product $F_0\cdots F_{n-1}$, hence divides $F_n-2$; and $q$ divides $F_n$. So $q\mid 2$. But every $F_n$ is odd, so $q$ is odd. Contradiction.

The $F_n$ are therefore pairwise coprime, and each one contributes at least one prime that no other contributes. Infinitely many primes.

What it gives you beyond Euclid

An explicit, infinite, effectively computable family of pairwise-coprime numbers. You can name a distinct prime for every $n$ with no search at all, whereas Euclid's construction hands you $N$ and leaves you to factor it — which in general is hard.

Goldbach sent this argument to Euler in 1730. Fermat's own guess that every $F_n$ is prime turned out to be wrong at the very first case he could not check, $F_5=641\times 6700417$, but the coprimality is untouched by that.

Topologize $\mathbb{Z}$ by taking the two-way infinite arithmetic progressions
$$S(a,b)=\{an+b:n\in \mathbb{Z}\},a\ne 0,$$
as a basis. This really is a basis: if $c\in S(a_1,b_1)\cap S(a_2,b_2)$ then $c\in S(\mathrm{lcm}(a_1,a_2),c)$, which lies inside both.

Two observations.

1. Every nonempty open set is infinite, since it contains some progression.
2. Every $S(a,b)$ is also closed, because its complement is the union of the other $a-1$ progressions modulo $a$ — a union of open sets.

Every integer other than $\pm 1$ has a prime divisor, so
$$\mathbb{Z}\setminus \{-1,1\}=\bigcup _{p\text{ prime}}S(p,0).$$

If there were only finitely many primes, the right-hand side would be a finite union of closed sets, hence closed, and $\{-1,1\}$ would be open. But it is finite and nonempty, which observation (1) forbids.

Is the topology doing any work?

Honestly, no — and that is the most interesting thing about it. Strip the vocabulary away and what remains is a counting argument about arithmetic progressions and inclusion–exclusion, close to Euler's. Hillel Furstenberg was an undergraduate when he published this, and its fame rests on the surprise of the framing rather than on any new content.

Which makes it a useful test case for this board. It is correct, it is unforgettable, and it is arguably the least explanatory proof on this page. Persuasion and explanation are not the same axis, and I think we should be honest that votes here will measure the first.