Welcome back to Numberholic! I’m your host, Sejari, and it’s always a pleasure to have you here. Today, we’re diving into the twelfth episode of Proven Yet Hard to Believe, a series where we uncover the fascinating stories and directly explore the core ideas behind mathematical discoveries that have stood the test of time.
Today, we will introduce a proof of the infinitude of prime numbers, known for being one of the simplest and most elegant proofs in Euclid’s Elements.
Proposition 20 in Book 9 of Euclid’s Elements states: “The number of prime numbers is infinite.” More precisely, “It is not finite.” In other words, if we assume there are only finitely many prime numbers, we can always find a new prime number.
Euclid demonstrates this by considering a few prime numbers and proving that a new prime must exist. Generalizing Euclid’s proof gives the following argument:
Assume there is a finite set of prime numbers.
Compute their product.
Add one to this product.
This new number is either prime or composite.
If it is prime, it is a new prime not in the original list.
If it is composite, consider any of its prime factors. If this factor is in the original list, it must divide both the Q and the Q minus one, meaning it must divide one—a contradiction. Hence, the prime factor is a new prime not in the given list.
Euclid’s method can also be viewed from another perspective:
Consider a set of prime numbers and find a number that leaves a remainder of 1 when divided by each of them.
Multiplying all the primes together and adding 1 results in a number that leaves a remainder of 1 when divided by any prime in the list.
In this discussion, we will modify this approach slightly to introduce a new method. Instead of fixing the remainder at 1, we will explore different remainders, as long as they do not result in divisibility. This idea leads us to an important concept: the Chinese Remainder Theorem.
The Chinese Remainder Theorem first appeared in the 5th-century Chinese mathematical text Sunzi Suanjing (“Master Sun’s Arithmetic Classic”). It is found in Chapter 3, Problem 26 of the second volume:
“There are an unknown number of objects. When counted in threes, two remain. When counted in fives, three remain. When counted in sevens, two remain. How many objects are there?”
The answer is 23. The solution method follows these steps:
If the remainder is 2 when divided by 3, write 140.
If the remainder is 3 when divided by 5, write 63.
If the remainder is 2 when divided by 7, write 30.
Adding these numbers gives 233. Subtracting 210 (the least common multiple of 3, 5, and 7) gives the final answer, 23.
Although the author of Sunzi Suanjing is unknown, the explanation provided does not include a proof or a general problem-solving strategy. The numbers 140, 63, and 30 seem to be derived from the values:
70 (a multiple of 5 and 7, leaving remainder 1 when divided by 3),
21 (a multiple of 7 and 3, leaving remainder 1 when divided by 5),
15 (a multiple of 3 and 5, leaving remainder 1 when divided by 7).
Remarkably, this method can be used to construct a proof, and modern number theory textbooks still employ it. Fascinating, isn’t it?
Now, let’s use the Chinese Remainder Theorem to discover new prime numbers and directly confirm the infinitude of primes. Instead of Sunzi’s method, we will use a more straightforward approach.
For example, consider the primes 2, 3, 5, and 7. We define remainders as 1, 2, 3, and 4, respectively. Any number satisfying these conditions must be:
A number that leaves a remainder of 1 when divided by 2: 1, 3, 5, 7, 9, 11, …
Among these, one that leaves a remainder of 2 when divided by 3: 5, 11, 17, 23, 29, 35, …
Among these, one that leaves a remainder of 3 when divided by 5: 23, 53, 83, …
Among these, one that leaves a remainder of 4 when divided by 7: 53 (which happens to be prime).
If we instead chose remainders 1, 2, 3, and 3, the sequence would be:
23, 53, 83, 113, 143, …
143 is not prime (it factors as 11 × 13), but 11 and 13 were not in our original list.
This method allows us to assert the existence of new primes. By setting the remainders to 1, 1-2, 1-4, and 1-6 for 2, 3, 5, and 7 respectively, we can explore 1 × 2 × 4 × 6 = 48 different cases.
Multiples of numbers appear in highly regular patterns, making primes symbols of irregularity. The infinitude of primes implies that such irregularities must always exist. These methods provide simple proofs of this infinite nature.
Using the Chinese Remainder Theorem in this way is a structured adaptation of Euclid’s approach, but both methods have two key limitations:
We cannot predict whether the resulting number will be prime.
The numbers generated tend to be quite large.
For example, consider the six primes 2, 3, 5, 7, 11, and 13:
Euclid’s method gives 2 × 3 × 5 × 7 × 11 × 13 + 1 = 30,031, which factors as 59 × 509.
Using the Chinese Remainder Theorem with remainders 1, 2, 3, 4, 5, and 6, we obtain:
53, 263, 473, 893, 1103, 1313, 1523, …
1523, 3833, 6143, 8453, 10763, 13073, 15383, 17693, 20003, 22313, 24623, 26933, 29243, …
Here, 29243 is prime.
Choosing remainders strategically might yield smaller numbers, but it remains challenging.
In the next episode, we will explore a modern perspective on the infinitude of prime numbers.