Prime numbers are the basic units of numbers, much like bricks in a skyscraper. Clearly, the fact that there are infinitely many primes is a prerequisite for the value of number theory research. Otherwise, the study of numbers would be limited to a finite set of primes, and many numbers would lose their charm. It would be like having only a finite number of bricks, which would make it impossible to create architectural wonders. Below, I will introduce two classic proofs regarding the infinitude of primes. One is Euclid’s proof, which is the most original and simplest method; I believe many readers have already learned it, but it is still worth mentioning here. The other is one I saw in How to Solve It, originally by Euler, which is also a very beautiful proof. Of course, this article emphasizes the ideas, and the argumentation process may have some informalities; readers are welcome to refine them. ^_^
Euclid’s Proof
The idea of this proof is very simple: the product of several primes plus 1 produces a new prime factor. If there were only n primes, what would happen if we multiplied them all together and added 1? If the result is a prime number, it contradicts the assumption that there are only n primes. If it is a composite number, it is not divisible by any of the original n primes (the remainder is always 1), so it must possess a new prime factor, which again contradicts the assumption of only n primes. In either case, assuming the number of primes is finite leads to a contradiction. Therefore, the number of primes must be infinite.
Euler’s Classic Proof
This proof requires some preparation. Its core idea is: Geometric Series + Generating Functions.
First, we have the formula S(p)=1+p^{-1}+p^{-2}+\dots+p^{-n}=\frac{1-p^{-n-1}}{1-p^{-1}}. This is the sum formula for a geometric series. When |p| > 1 and n \to \infty, then p^{-n-1} \to 0, and we have: S(p)=\sum_{n=0}^{\infty} p^{-n}=\frac{1}{1-p^{-1}}=\frac{p}{p-1}
Next, we attempt to let p range over all prime numbers, i.e., 2, 3, 5, 7, \dots, and multiply each S(p) together to get (denoted as K): \begin{aligned}K &= S(2) \cdot S(3) \cdot S(5) \dots \\ &= \left(1+\frac{1}{2}+\frac{1}{2^2}+\frac{1}{2^3} \dots\right)\left(1+\frac{1}{3}+\frac{1}{3^2}+\frac{1}{3^3} \dots\right)\left(1+\frac{1}{5}+\frac{1}{5^2}+\frac{1}{5^3} \dots\right) \dots \\ &= \frac{2}{2-1} \cdot \frac{3}{3-1} \cdot \frac{5}{5-1} \cdot \dots\end{aligned}
What is special about K? Notice that here the powers of each prime are multiplied with each other exactly once. This is identical to how natural numbers are generated: By multiplying the powers of several primes, one can obtain any natural number. Thus, we can write (not without foundation): K=1+\frac{1}{2}+\frac{1}{3}+\frac{1}{4}+\frac{1}{5}+\dots
As we know, the series 1+\frac{1}{2}+\frac{1}{3}+\frac{1}{4}+\frac{1}{5}+\dots (the harmonic series) diverges. Therefore, it is impossible for there to be only a finite number of primes. If there were only finitely many primes, then the product K = \frac{2}{2-1} \cdot \frac{3}{3-1} \cdot \frac{5}{5-1} \cdot \dots would necessarily be finite, leading to a contradiction. Thus, primes are infinite.
A Connection to the Prime Number Theorem
The Prime Number Theorem tells us that the number of primes not exceeding n, denoted by \pi(n), is approximately equal to \frac{n}{\ln n}.
From the discussion above, we obtained: K = \frac{2}{2-1} \cdot \frac{3}{3-1} \cdot \frac{5}{5-1} \cdot \dots = 1+\frac{1}{2}+\frac{1}{3}+\frac{1}{4}+\frac{1}{5}+\dots
Using calculus, it can be proven that the part on the right side of the second equals sign, 1+\frac{1}{2}+\frac{1}{3}+\frac{1}{4}+\frac{1}{5}+\dots+\frac{1}{n}, can be approximated as \ln n. By inverting the expression, we get: \frac{2-1}{2} \cdot \frac{3-1}{3} \cdot \frac{5-1}{5} \cdot \dots \approx \frac{1}{\ln n}
For a large n, the number of even numbers not exceeding n is clearly about n/2. Among the remaining n/2 odd numbers, the multiples of 3 are about 1/3, so the non-multiples of 3 are about n \cdot 1/2 \cdot 2/3. Among the remaining numbers, the non-multiples of 5 are about n \cdot 1/2 \cdot 2/3 \cdot 4/5. Following this logic, we get: \pi(n) \approx n \cdot 1/2 \cdot 2/3 \cdot 4/5 \cdot 6/7 \cdot \dots \approx \frac{n}{\ln n}
Of course, this is not a rigorous proof at all; at most, it is a strained but luckily successful piece of reasoning. However, even though it cannot withstand the test of strict logic, it is quite interesting as an elementary piece of thinking to appreciate. ^_^
When reposting, please include the original address: https://kexue.fm/archives/1484
For more detailed information on reposting, please refer to: Scientific Space FAQ