# 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?

-
That first proof is Euclid's, not Euler's. – Gerry Myerson Jul 7 '11 at 4:42
Chapter 1 of Aigner-Ziegler, Proofs from THE BOOK contains six proofs (most of them were already mentioned, though). – t.b. Jul 7 '11 at 5:02
@Patrick: it is strange that, having asked for proofS, you accepted one answer... – Mariano Suárez-Alvarez Jul 7 '11 at 5:09
I just want to note here, that Euclid's proof was in fact both direct and constructive. – Alexander Thumm Jul 7 '11 at 5:19
Euclid's proof is misrepresented here, as it is by many illustrious authors. Euclid never assumed there are only finitely many; his proof was not by contradiction Catherine Woodgold and I published a paper about this misunderstanding: "Prime Simplicity", Mathematical Intelligencer, Volume 31, Number 4, 44-52, DOI: 10.1007/s00283-009-9064-8 – Michael Hardy Nov 17 '11 at 1:13

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.

-
 Didn't think of the ones with Euler products, I never came across those. Thanks for both proofs! – Patrick Da Silva Jul 7 '11 at 5:00 @Patrick: well, this is just a simplified version of an argument about the zeta function, and such arguments are of course the heart of the proof of Dirichlet's theorem. – Qiaochu Yuan Jul 7 '11 at 5:11

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.

-
One can write down the same proof with Apéry's theorem and $\zeta(3)$, but that is really overkill... – Qiaochu Yuan Jul 7 '11 at 5:17

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}]$.

-
 +1 I like this argument! – Amitesh Datta Jul 7 '11 at 12:12 I must admit I don't know anything about algebraic number theory to understand your argument, but I'll be taking a course this year about that so I guess I'll read it later on. =) +1 – Patrick Da Silva Jul 7 '11 at 20:17 By the way, maybe I should say that I didn't give all eight proofs in my lectures (or maybe I shouldn't, so that people will think that I cover everything in my classes that appears in my lecture notes: that would be pretty impressive). This proof I either skip entirely or summarize as "Actually, it is possible to deduce the infinitude of the prime numbers directly from the lack of unique factorization in $\mathbb{Z}[\sqrt{-5}]$, but this requires methods from more advanced number theory." – Pete L. Clark Jul 7 '11 at 20:40

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)

-
I don't remember seeing this proof. I like it a lot. – Geoff Robinson Jul 7 '11 at 17:18
Yes, it's quite nice. It can be extracted from the sixth proof in Proofs from the Book, which is also attributed to Erdős. It is a stronger version of the counting proof I gave and gives a slightly stronger "weak PNT." – Qiaochu Yuan Jul 7 '11 at 18:50
I like the following slight rephrasing. Suppose the number of primes is finite, say $C$. Every $n\in\{1,\ldots,N\}$ can be written uniquely in the form $k^2\ell$ where $\ell$ is a product of distinct primes. The number of choices for $k$ is at most $\sqrt{N}$, and the number of choices for $\ell$ is at most $2^C$. Therefore the number of integers in $\{1,\ldots,N\}$ is at most $2^C\sqrt{N}$, which clearly cannot remain true as $N$ increases. – idmercer Jul 8 '11 at 0:44
I prefer his phrasing, no offense. – Patrick Da Silva Jul 9 '11 at 22:16

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.

-
I added two links to Fürstenberg's proof. I hope you don't mind. – t.b. Jul 7 '11 at 4:52
Whew. Nice. Seriously, reading all those proofs, I remember other proofs. XD Giving you the green check Qiao :) thanks a lot – Patrick Da Silva Jul 7 '11 at 5:03
@Patrick: don't take this the wrong way, but I don't really understand the point of accepting an answer to a big-list question... – Qiaochu Yuan Jul 7 '11 at 5:11
It's just a way of giving extra rep. I'm being thankful. You gave me like four proofs. – Patrick Da Silva Jul 7 '11 at 5:23
@Patrick: I think you will get more answers if you don't accept an answer. More answers accumulating means more people get to learn about interesting proofs, which is much more important than reputation. I'm not sure accepting CW answers gives reputation, and even if it did I don't really need it... – Qiaochu Yuan Jul 7 '11 at 5:24

Source : Proofs from the Book, by Martin Aigner and Günter M. Ziegler.

Here is one more proof. I don't really know who discovered it.

Let $\pi(x) = \# \bigl\{ \text{No of primes} \ \leq x \bigr\}$. Suppose $p$ is the largest element. We consider the Mersenne number $2^{p}-1$, and show that for any prime factor $q$ of $2^{p}-1$ is bigger than $p$. So let $p$ be a prime dividing $2^{p}-1$. So we have $2^{p} \equiv 1 \ (\text{mod} \ q)$. Since $p$ is prime, his means that, the element $2$ has order $p$ in the multiplicative group $\mathbb{Z}_{q}\setminus \{0\}$ of the field $\mathbb{Z}_{q}$. This group has $q-1$ elements, so by Lagrange's theorem, we know that the order of every element divides the order of the group. Hence $p \mid (q-1)$, which shows that $p < q$.

$\text{Added.}$

-
Ugh. Chandru, you have been warned time and time again about citing your sources. This is, nearly word for word, the second proof in Proofs from the Book. – Qiaochu Yuan Jul 7 '11 at 5:27
@chandru: "How am I to remember the fact where I had taken this from." You don't seem to understand that it is your responsibility to remember this, or at least not to reproduce things when you know you have a habit of verbatim copying. This same attitude applied to your written work would get you kicked out of many if not most universities. – Pete L. Clark Jul 7 '11 at 6:40
Here is the source. As Qiaochu said, it is almost verbatim copying. – Zev Chonoles Jul 7 '11 at 6:55
Saying you don't know to whom the proof is due allows for the possibility that you wrote up the argument yourself. (For instance, a mathematically equivalent version of this same proof appears in the document linked to in my answer, but the argument has been rewritten in my own words.) Even to say "I took this almost verbatim from somewhere, but I can't remember where" is not a good practice, because you took the time to copy something without taking the care to record what you were copying. If others can catch you out, then with the same amount of effort you can retrieve your sources. – Pete L. Clark Jul 7 '11 at 7:39
@Chandru: the post is much better now. Thank you for taking our concerns seriously. – Pete L. Clark Jul 9 '11 at 15:20

There's a collection at http://primes.utm.edu/notes/proofs/infinite/

-
 Actually four of the five proofs there are in my question, but I like the fifth one! – Patrick Da Silva Jul 7 '11 at 5:00

The following proof can be extracted from Erdős' proof of Bertrand's postulate (although perhaps this argument should be credited to Chebyshev). We need the following two lemmas from that page.

Lemma 1: ${2n \choose n} > \frac{4^n}{2n+1}$.

Lemma 2: The greatest power $R(p, n)$ of a prime $p$ dividing ${2n \choose n}$ satisfies $p^{R(p, n)} \le 2n$.

From these two lemmas it follows that

$$\frac{4^n}{2n+1} < {2n \choose n} \le (2n)^{\pi(2n)}$$

which is a contradiction for large $n$ if $\pi(2n)$ is bounded. This gets us within a constant of the PNT:

$$\pi(2n) \ge \frac{n \log 4 - \log (2n+1)}{\log 2n}.$$

-

One proof approach is to construct an infinite set of numbers, any two of which are relatively prime. The proof using Fermat numbers/Euclid's proof can be considered to follow that approach (so I am not sure if I should even be adding this answer!).

We construct a set explicitly as follows.

Start with $3$. Now if we already have $\{x_1, x_2, \dots, x_n\}$ so far, whose prime divisors are $\{p_1, p_2, \dots, p_r\}$, take $x_{n+1} = 2^{(p_1 -1)(p_2 - 1) \dots (p_r - 1)} + 1$

By Fermat's little theorem, $x_{n+1} = 1 \mod p_i$ and thus is relative prime to each $x_i$.

Incidentally the Fermat numbers are relative co-prime can also be proved as follows:

If $x = 2^{2^m}$ and $2^{2^m} + 1 = 0 \mod p$, (i.e. $x = -1 \mod p$) then since $2^{2^{n}}$ is an even power of $x$, we have that $2^{2^n} + 1 = 2 \mod p$.

-
 This is the idea behind the two proofs in my question ; the one with the sequence $2^{2^n}+1$ and the other one with the Chinese Remainder Theorem. But the approach with your $x_{n+1}$ I didn't know, thanks. – Patrick Da Silva Jul 7 '11 at 20:14

Another well-known proof which is somewhat related to two of the proofs by Qiaochu above is to note that for every prime $p \leq n$, the power of $p$ dividing $n!$ is at most $p^{\frac{n-1}{p-1}}$. Since certainly $p^{\frac{1}{p-1}} \leq 2$, we obtain that $2^{n \pi(n)} > n!$, where $\pi(n)$ is the number of primes less than or equal to $n$. Using Stirling's formula shows that $\pi(n) \to \infty$ as $n \to \infty$. A more careful version of this argument goes back to Chebyshev.

In an AMM paper ( around 1954) called "A Method for finding primes", John Thompson came up with a simple, but very nice, variant of Euclid's argument: if we list a set of distinct primes, $\{p_1,p_2,\ldots, p_n\}$, not necessarily in increasing order, then for any $k \leq n$, the integer $p_1 \ldots p_k - p_{k+1}\ldots p_n$ is not divisible by any of the given $p_i$. This may be $\pm 1$, of course, but in that case you can interchange various $p_i$'s. The point is that you get lots more primes not in your original list this way, and they are divisors of numbers not necessarily so much larger than the primes you start with.

-
You don't need the full strength of Stirling's formula; using the fact that $e^x \ge \frac{x^n}{n!}$ for $x \ge 0$ we get $e^n \ge \frac{n^n}{n!}$ or $n! \ge \left( \frac{n}{e} \right)^n$. I learned this argument from Terence Tao's very nice post here: terrytao.wordpress.com/2010/01/02/… – Qiaochu Yuan Jul 7 '11 at 13:16
Yes. Nice simplification, thanks. – Geoff Robinson Jul 7 '11 at 13:50

This is taken from Section 1.4 of Andrew Granville's notes on Prime numbers:

We finish this section by proving that for any $f(t) \in \mathbb Z[t]$ of degree $\ge1$ there are infinitely many distinct primes $p$ for which $p$ divides $f(n)$ for some integer $n$. We may assume that $f(n) \ne 0$ for all $n \in \mathbb Z$ else we are done. Now suppose that $p_1,\ldots,p_k$ are the only primes which divide values of $f$ and let $m = p_1 \cdots p_k$. Then $f(nmf(0)) \equiv f(0) \pmod{mf(0)}$ for every integer $n$, by exercise 1.2a.a, so that $f(nmf(0))/f(0) \equiv 1 \pmod m$. Therefore $f(nmf(0))$ has prime divisors other than those dividing $m$ for all $n$ but the finitely many $n$ which are roots of $(f(tmf(0)) - f(0))(f(tmf(0)) + f(0))$, a contradiction.

Exercise 1.2a.a is: Prove that if $f(t) \in \mathbb Z[t]$ and $r,s\in\mathbb Z$ then $r-s$ divides $f(r)-f(s)$.

Other parts of his course notes might be interesting in connection with this question, too.

-
Funny you should say that, Andrew's my advisor. XD Thanks! – Patrick Da Silva Nov 27 '11 at 18:19

The following proof use the Euler's totient function and relies on the fact that $\phi(m) > 1$ for all $m \geq 3$.

Assume that there are only a finite number of primes say $p_1,p_2,\ldots,p_k$. Look at the product of these finite primes i.e. $$m = p_1 p_2 \cdots p_k$$ Now consider any number $n > 1$. Since there are only finite primes, one of the $p_j$'s must divide $n$. Hence, $\gcd(m,n) > 1$. Hence, $\phi(m) = 1$ contradicting the fact that $\phi(m) > 1$ for all $m \geq 3$.

-

Maybe you wanna use the sum of reciprocal prime numbers. The argument for the fact that
the series diverges you may find here in one of Apostol's exercise.

-