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 p1p2...pn+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 an=22n+1. We have that
so that for m<n, (22m+1,22n+1)|(22n1,22n+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 Z in the following way : a set N of integers is said to be open if for every nN there is an arithmetic progression A such that nAN. This can easily be proven to define a topology on 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
should be open and closed, but by the fundamental theorem of arithmetic, its complement in 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 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.

Source : Link , Question Author : Community , Answer Author :
Qiaochu Yuan

Leave a Comment