素数无穷多的证明

hbghlyj

The new book of prime number records, Paulo Ribenboim, 1996
I. Euclid's Proof

Euclid's Proof.

Suppose that $p_{1}=2<p_{2}=3<\cdots<p_{r}$ are all the primes. Let $P=p_{1} p_{2} \cdots p_{r}+1$ and let $p$ be a prime dividing $P$; then $p$ cannot be any of $p_{1}, p_{2}, \ldots, p_{r}$, otherwise $p$ would divide the difference $P-p_{1} p_{2} \cdots p_{r}=1$, which is impossible. So this prime $p$ is still another prime, and $p_{1}, p_{2}, \ldots, p_{r}$ would not be all the primes. ■

Euclid's proof is pretty simple; however, it does not give any information about the new prime found in each stage, only that it is at most equal to the primes already found. Thus, it may be that $P=p_{1} p_{2} \cdots p_{n}+1$ is itself a prime (for some $n$), or that it is composite (for other indices $n$). I shall examine this and similar questions in Section VIII of this chapter.

Euclid's proof has of course many variants. Here is one: Let $q_{1}=3, q_{2}=q_{1}-1=2, q_{3}=q_{1} q_{2}-1=5$; more generally let $q_{n+1}$ be a prime dividing $Q=q_{1} q_{2} \cdots q_{n}-1$. Then $q_{n+1}$ is different from $q_{1}, \ldots, q_{n}$, so the process may be continued and gives a proof that there are infinitely many primes.

Another very elegant variant was given by Kummer in 1878 .

Kummer's Proof.

Suppose that there exist only finitely many primes $p_{1}<p_{2}<\cdots<p_{r}$. Let $N=p_{1} p_{2} \cdots p_{r}>2$. The integer $N-1$, being a product of primes, has a prime divisor $p_{i}$ in common with $N$; so, $p_{i}$ divides $N-(N-1)=1$, which is absurd! ■

This proof, by an eminent mathematician, is like a pearl, round, bright, and beautiful in its simplicity.

A proof similar to Kummer's was given in 1890 by Stieltjes, another great mathematician.

Stieltjes' Proof.

Assume that $p_{1}, p_{2}, \ldots, p_{r}$ are the only existing primes. Let $N=p_{1} p_{2} \cdots p_{r}$ and let $N=m n$ be any factorization of $N$ (with $1 \leq m, n$). Each prime $p_{i}$ divides one, but not both, numbers $m, n$. Then $m+n$ is not divisible by any of the existing primes, which is absurd since $m+n \neq 1$. ■

II. Goldbach Did It Too!
The idea behind the proof is very simple and fruitful. It is enough to find an infinite sequence of natural numbers $a_{1}, a_{2}, \ldots, a_{n}, \ldots$, greater than 1 , that are pairwise relatively prime (i.e., without a common prime factor). So, if $q_{1}$ is a prime dividing $a_{1}$, if $q_{2}$ is a prime dividing $a_{2}$, etc., then $q_{1}, q_{2}, \ldots$ are all different.
The point is that the greatest common divisor is calculated by successive Euclidean divisions and this does not require knowledge of the prime factors of the numbers.

Nobody seems to be the first to have a good idea–especially if it is simple. I thought it was due to Pólya and Szegö (see their book, 1924). E. Specker called my attention to the fact that Pólya used an exercise by Hurwitz (1891). But, W. Narkiewirz just told me that in a letter to Euler (July 20/31,1730), Goldbach wrote the proof given below using Fermat numbers–this may well be the only written proof of Goldbach.

The Fermat numbers $F_{n}=2^{2^{n}}+1$ (for $n \geq 0$) are pairwise relatively prime.

Proof.

It is easy to see, by induction on $m$, that $F_{m}-2=F_{0} F_{1} \cdots F_{m-1}$; hence, if $n<m$, then $F_{n}$ divides $F_{m}-2$.

If a prime $p$ would divide both $F_{n}$ and $F_{m}$, then it would divide $F_{m}-2$ and $F_{m}$, hence also 2 , so $p=2$. But $F_{n}$ is odd, hence not divisible by 2 . This shows that the Fermat numbers are pairwise relatively prime. ■

Explicitly, the first Fermat numbers are $F_{0}=3, F_{1}=5, F_{2}=17, F_{3}=257, F_{4}=65537$, and it is easy to see that they are prime numbers. $F_{5}$ already has 10 digits, and each subsequent Fermat number is about the square of the preceding one, so the sequence grows very rapidly. An important problem has been to find out whether $F_{n}$ is a prime, or at least to find a prime factor of it. I shall return to this point in Chapter 2 .

There are again many variants using the idea of Hurwitz. Here is one: Let $w_{1}=2, w_{2}=w_{1}+1=3, w_{3}=w_{1} w_{2}+1=7, \ldots, w_{n+1}=\prod_{i=1}^{n} w_{i}+1$. The numbers $w_{1}, w_{2}, \ldots, w_{n}, \ldots$ are pairwise relatively prime. So if $q_{n}$ is a prime dividing $w_{n}$, the primes $q_{1}, q_{2}, \ldots, q_{n}, \ldots$ are all distinct.

I shall look more closely at the sequence $\left(w_{n}\right)_{n \geq 1}$ and similar sequences in the last section of this chapter.

I wish to thank P. Schorn, who communicated to me the following proof, which is based on Hurwitz's idea.
First, one notes: If $1 \leq i<j \leq n$, then
$$
\operatorname{gcd}((n !) i+1,(n !) j+1)=1 \text {. }
$$
Indeed, $j=i+d$, with $1 \leq d<n$, so
$$
\operatorname{gcd}((n !) i+1,(n !) j+1)=\operatorname{gcd}((n !) i+1,(n !) d)=1 \text {. }
$$

Proof of Schorn

Assume that there exist only $m$ prime numbers; let $n=m+1$. The preceding remark tells us that the $n$ integers $(n !) i+1$ (for $i=1,2, \ldots, n)$ are pairwise relatively prime. If $p_{i}$ is a prime dividing $(n !) i+1$, then $p_{1}, p_{2}, \ldots, p_{n}$ are distinct primes, with $n=m+1$, which is absurd! ■

III. Euler's Proof
This is a rather indirect proof which, in some sense, is unnatural; but, on the other hand, as I shall indicate, it leads to the most important developments.

Euler showed that there must exist infinitely many primes because a certain expression formed with all the primes is infinite.

If $p$ is any prime, then $1 / p<1$; hence, the sum of the geometric series is
$$
\sum_{k=0}^{\infty} \frac{1}{p^{k}}=\frac{1}{1-(1 / p)} .
$$
Similarly, if $q$ is another prime, then
$$
\sum_{k=0}^{\infty} \frac{1}{q^{k}}=\frac{1}{1-(1 / q)} .
$$
Multiplying these equalities:
$$
1+\frac{1}{p}+\frac{1}{q}+\frac{1}{p^{2}}+\frac{1}{p q}+\frac{1}{q^{2}}+\cdots=\frac{1}{1-(1 / p)} \times \frac{1}{1-(1 / q)} .
$$
Explicitly, the left-hand side is the sum of the inverses of all natural numbers of the form $p^{h} q^{k}(h \geq 0, k \geq 0)$, each counted only once, because every natural number has a unique factorization as a product of primes. This simple idea is the basis of the proof.

Euler's Proof.

Suppose that $p_{1}, p_{2}, \ldots, p_{n}$ are all the primes. For each $i=1, \ldots, n$,
$$
\sum_{k=0}^{\infty} \frac{1}{p_{i}^{k}}=\frac{1}{1-\left(1 / p_{i}\right)} .
$$
Multiplying these $n$ equalities, one obtains
$$
\prod_{i=1}^{n}\left(\sum_{k=0}^{\infty} \frac{1}{p_{i}^{k}}\right)=\prod_{i=1}^{n} \frac{1}{1-\left(1 / p_{i}\right)},
$$
and the left-hand side is the sum of the inverses of all natural numbers, each counted once–this follows from the fundamental theorem that every natural number is equal, in a unique way, to the product of primes.

But the series $\sum_{n=1}^{\infty}(1 / n)$ is divergent; being a series of positive terms, the order of summation is irrelevant, so the left-hand side is infinite, while the right-hand side is clearly finite. This is absurd. ■
In Chapter 4, I will return to developments along this line.

IV. Thue's Proof
Thue's proof uses only the fundamental theorem of unique factorization of natural numbers as products of prime numbers.

Thue's Proof.

First let $n, k \geq 1$ be integers such that $(1+n)^{k}<2^{n}$. Let $p_{1}=2, p_{2}=3, p_{3}, \ldots, p_{r}$ be all the primes satisfying $p \leq 2^{n}$. Suppose that $r \leq k$.

By the fundamental theorem, every integer $m, 1 \leq m \leq 2^{n}$, may be written in a unique way in the form
$$
m=2^{e_{1}} 3^{e_{2}} \cdots p_{r}^{e_{r}},
$$
where $0 \leq e_{1} \leq n, 0 \leq e_{2} < n, \ldots, 0 \leq e_{r}<n$.
Counting all the possibilities, it follows that $2^{n} \leq(n+1) n^{r-1}<(n+1)^{r} \leq(n+1)^{k}<2^{n}$, and this is absurd. So $r \geq k+1$.

Choose $n=2 k^{2}$. From $1+2 k^{2}<2^{2 k}$ for every $k \geq 1$, it follows that
$$
\left(1+2 k^{2}\right)^{k}<2^{2 k^{2}}=4^{k^{2}} .
$$
Thus, there exist at least $k+1$ primes $p$ such that $p<4^{k^{2}}$. ■
Since $k$ may be taken arbitrarily large, this shows that there are infinitely many primes, and that $k+1$ is actually a lower bound for the number of primes less than $4^{k^{2}}$. This is a quantitative result, which is, of course, very poor. In Chapter 4 , I shall further investigate this kind of question.

V. Three Forgotten Proofs
The next proofs are by Perott, Auric, and Métrod. Who remembers these names? If it were not for Dickson's History of the Theory of Numbers, they would be totally forgotten. As I shall show, these proofs are very pleasant and ingenious; yet, they do not add new insights.
A. Perott's Proof
Perott's proof dates from 1881.

Perott's Proof.

It is required to know that $\sum_{n=1}^{\infty}\left(1 / n^{2}\right)$ is convergent with sum smaller than 2. (As a matter of fact, it is a famous result of Euler that the sum is exactly $\pi^{2} / 6$, and I shall return to this point in Chapter 4.)
Indeed,
$$
\sum_{n=1}^{\infty} \frac{1}{n^{2}}<1+\sum_{n=1}^{\infty} \frac{1}{n(n+1)}=1+\sum_{n=1}^{\infty}\left(\frac{1}{n}-\frac{1}{n+1}\right)=1+1=2
$$
Let
$$
\delta=2-\sum_{n=1}^{\infty} \frac{1}{n^{2}} .
$$
Suppose that there exist only $r$ prime numbers $p_{1}<p_{2}<\cdots<p_{r}$. Let $N$ be any integer such that $p_{1} p_{2} \cdots p_{r}<N$. The number of integers $m \leq N$ that are not divisible by a square is therefore $2^{r}$ (which is the number of all possible sets of distinct primes), because every integer is, in a unique way, the product of primes. The number of integers $m \leq N$ divisible by $p_{i}^{2}$ is at most $N / p_{i}^{2}$; so the number of integers $m \leq N$ divisible by some square is at most $\sum_{i=1}^{r}\left(N / p_{i}^{2}\right)$. Hence,
$$
N \leq 2^{r}+\sum_{i=1}^{r} \frac{N}{p_{i}^{2}}<2^{r}+N\left(\sum_{n=1}^{\infty} \frac{1}{n^{2}}-1\right)=2^{r}+N(1-\delta)
$$
By choosing $N$ such that $N \delta \geq 2^{r}$, it follows a contradiction. ■

B. Auric's Proof
Auric's proof, which appeared in 1915, is very simple.

Auric's Proof.

Suppose that there exist only $r$ primes $p_{1}<p_{2}<\cdots<p_{r}$. Let $t \geq 1$ be any integer and let $N=p_{r}^{t}$.

By the unique factorization theorem, each integer $m, 1 \leq m \leq N$, is written $m=p_{1}^{f_{1}} p_{2}^{f_{2}} \cdots p_{r}^{f_{r}}$ and the sequence $\left(f_{1}, \ldots, f_{r}\right)$, with each $f_{i} \geq 0$, is uniquely defined. Note also that $p_{1}^{f_{i}} \leq m \leqN=p_{r}^{t}$. Letting $E=\left(\log p_{r}\right) /\left(\log p_{1}\right)$, then $f_{i} \leq t E$. Thus, the number $N$ (of integers $m, 1 \leq m \leq N$ ) is at most the number of sequences $\left(f_{1}, f_{2}, \ldots, f_{r}\right)$; hence, $p_{r}^{t}=N \leq(t E+1)^{r} \leq t^{r}(E+1)^{r}$. If $t$ is sufficiently large, this inequality cannot hold, which shows that the number of primes must be infinite. ■

C. Métrod's Proof
Métrod's proof of 1917 is also very simple.

Métrod's Proof.

Assume that there exist only $r$ primes $p_{1}<p_{2}<\cdots<p_{r}$. Let $N=p_{1} p_{2} \cdots p_{r}$, and for each $i=1, \ldots, r$, let $Q_{i}=N / p_{i}$. Note that $p_{i}$ does not divide $Q_{i}$, while $p_{i}$ divides $Q_{j}$, for all $j \neq i$. Let $S=\sum_{i=1}^{r} Q_{i}$. If $q$ is any prime dividing $S$, then $q \neq p_{i}$ because $p_{i}$ divides $Q_{j}$ (for $j \neq i$) but $p_{i}$ does not divide $Q_{i}$. Thus there exists yet another prime! ■

Actually, Métrod's proof is no more than a variant of the proof of Stieltjes.

hbghlyj

A Short Generalized Proof of Infinitude of Primes, Jay Mehta
There are infinitely many primes.
Proof.

Assume $p_1,…,p_n$ are distinct primes, and let $P$ denote their product, i.e., $P=p_1⋯p_n$. Choose any factorization of $P$ into $k≥2$ terms, say $P=d_1⋯d_k$, and let
$$M=\frac P{d_1}+⋯+\frac P{d_k}.\tag1$$
Then $M$ is not divisible by any of $p_1,…,p_n$. Indeed, if $p$ is any of the prime $p_i$, then $p$ divides $d_j$ for exactly one $j$. Then $p$ divides every term on the right hand side of (1) with exactly one exception, namely $P\over d_j$. So $p$ does not divide the right hand side, and hence $p$ does not divide $M$. Since $M≥k≥2$, there is some prime dividing $M$, and hence there exists a prime other than $p_1,…,p_n$. This shows that no finite list of primes can be complete. ■

Remark.

取$k = 2$为1^#的Stieltjes的证明. 特别地, 取$k = 2, d_1=1, d_2=P$, 为Euclid的证明.
取$k=n$与$d_i=p_i(i=1,2,…,n)$得到Métrod (1917)的证明.

Czhang271828

Furstenberg's proof.

Define the topology on $\mathbb Z$, that is, open sets are generated by arithmetic sequences (in the form of $a\mathbb Z+b$). Let
\[
S(a,b):=a\mathbb Z+b:=\{an+b\mid n\in\mathbb Z\}.\]
Then $S(a,b)$ are both open and closed.

Assume that prime numbers are finite. Then $\cup_{p\text{ is prime}}S(p,0)$ is a finite union of closed sets, thus closed. As a result, $\{\pm 1\}=\mathbb Z-\cup_{p\text{ is prime}}S(p,0)$ is open. This would be a contradiction!