Earlier, we acquired an age-old but reliable weapon: proof by contradiction. However, this single weapon alone is not enough to prove the infinitude of prime numbers. Proof by contradiction is like a final weapon, a bomb that demolishes enemy strongholds. Relying solely on it and charging forward recklessly might lead to unexpected pitfalls. When proving that natural numbers are infinite, the simple principle that "if x is a natural number, then x+1 is also a natural number" sufficed. But to prove the infinitude of primes, we need a more refined and sophisticated tool.
Let’s first establish a few mathematical terms. An integer is a number that falls into the sequence ..., -3, -2, -1, 0, 1, 2, 3, ... without any decimal points. Consider any two integers. For example, taking 5 and 7, their sum is 12, their difference is -2, and their product is 35, all of which remain integers. This holds true for any pair of integers—their sum, difference, and product are always integers. We express this property by saying that "integers are closed under addition, subtraction, and multiplication." However, integers are not closed under division; for instance, dividing 5 by 7 gives 5/7, which is not an integer.1
When defining prime numbers, we often use the concept of "divisibility." We naturally say things like "4 is divisible by 2," "5 is not divisible by 2," and "since 5 is prime, it is only divisible by 1 and 5." However, someone might ask, "Why isn’t 5 divisible by 2? After all, 5/2 = 2.5." Even such an obvious and familiar concept as "divisibility" requires a precise definition!
From this definition, we derive the following facts:
3 divides 6 because there exists an integer such that (in this case, ).
3 does not divide 5 because there is no integer such that .
3 divides 0 because there exists an integer x such that (in this case, ).
3 divides because there exists an integer such that (in this case, ).
As a side note, any integer that is divisible by 2 (i.e., ) is called an even number. This definition includes and 0 as even numbers.
In science, important verified facts are called laws. In mathematics, they are called theorems. The difference lies in the methodology: science verifies laws through experiments and observations, whereas mathematics proves theorems using definitions and logic. Great theorems do not appear out of thin air. Just as magnificent castles require solid foundations, proving elegant theorems requires small yet essential preliminary facts. These facts are called lemmas. To prove the infinitude of primes, we first need the following lemma.
Let’s build intuition by looking at examples. For instance, 3 divides both 15 and 21, since there exist integers and such that and (specifically, and ). The difference is , and indeed, there exists an integer such that (in this case, ). Our intuition suggests that this lemma should be true. However, in the rigorous world of mathematics, examples merely illustrate special cases. To establish this property for all integers, we must prove it.
Proof. Since divides both and , by definition, there exist integers and such that and . Thus, .
Since and are integers and integers are closed under subtraction, is also an integer. Hence, there exists an integer such that , where . Therefore, divides . ◻
Thus, the proof is complete.2
Now, we are ready to prove that there are infinitely many prime numbers. We will use proof by contradiction, so we begin by assuming the opposite of our claim.
Proof. Suppose there are only finitely many primes. Then, there must be a largest prime, denoted by . Define as the product of all prime numbers: . That is, is divisible by all primes.
Consider the number . By the fundamental theorem of arithmetic, must be either prime or composite.
If is prime, then it is greater than , contradicting the assumption that is the largest prime.
If is composite, then it has some prime divisor . Since is the largest prime, must be one of .
Since divides (by definition of ), and also divides , our lemma implies that must divide . However, no prime number divides ! This contradiction proves that our assumption was false. Therefore, there must be infinitely many prime numbers. ◻
Let’s take a closer look at the core of this proof using a familiar example.
Suppose that the only prime numbers in the world are 2 and 3. Then, would be 7. Since 7 is a prime number greater than 3, our assumption leads to a contradiction.
If we assume that the only prime numbers are 2, 3, and 5, then would be 31. Since 31 is a prime number greater than 5, this also results in a contradiction.
If we assume that the only prime numbers are 2, 3, 5, and 7, or even 2, 3, 5, 7, and 11, then becomes 211 and 2311, respectively—both of which are prime numbers. Since they are greater than 7 and 11, respectively, we again reach a contradiction. A hasty reader might mistakenly conclude, "Oh, is always a prime number!"3
Now, suppose that the only prime numbers are 2, 3, 5, 7, 11, and 13. Then, would be 30,031, which is a composite number. However, none of 2, 3, 5, 7, 11, or 13 divides 30,031. The prime factorization of 30,031 is , and both of these numbers are prime numbers greater than 13. Thus, we once again arrive at a contradiction. This means that even if is a composite number, its prime factors must be greater than the "largest prime" we initially assumed.
This proof is an ancient one, appearing in Elements by Euclid around 300 BCE.4 While mathematics has since provided various proofs of the infinitude of prime numbers, none is as elegant and simple as this one. One might even say that it is the most outstanding proof, and that there will never be a more remarkable one.
By my standards, the next most beautiful proof is Euler’s. Euler showed that the sum of the reciprocals of prime numbers diverges to infinity. In other words, he demonstrated the following5:
Each term in this sum— and so on—is less than 1. If there were only a finite number of primes, then adding up finitely many values, each less than 1, could never result in infinity. Therefore, there must be infinitely many prime numbers. While this proof may appear more concise than Euclid’s, it requires first proving that the sum of the reciprocals of primes diverges to infinity.6