It has been known since at least Euclid’s time that there are an infinite number of prime numbers. Here is his basic proof:
Imagine that there is a finite set of prime numbers, P. Let N be the product of all the elements of P, plus 1. N’s factors do not include any element of P. Therefore either N is prime or N is a composite with factors outside of P. Either way, there must be prime numbers not in P. But since this is true for any finite set P, it must be the case that there are an infinite number of primes.
I’ve seen several discussions of this proof that interpret it to be saying that we can use Euclid’s proof to find primes larger than any currently known prime, but that’s not necessarily the case. It allows us to find a prime that’s not currently known, but that prime may be lower than the currently known maximum. Since our knowledge of primes includes some incredibly large numbers, and since we know that there are primes in the gaps between our known numbers, Euclid’s proof is not as useful as other methods for finding larger-than-known primes.
In 1963, Albert Mullin explored this proof by starting with the smallest prime (2) and building the set of primes from there (Mullin, Albert A. (1963), “Recursive function theory (A modern look at a Euclidean idea)”, Bulletin of the American Mathematical Society 69 (6): 737). This sequence jumps primes fairly quickly, but also doubles back as quickly:
- \(p_1 = 2\)
- \(p_2 = 2 + 1 = 3\)
- \(p_3 = (2 \cdot 3) + 1 = 7\)
- \(p_4 = (2 \cdot 3 \cdot 7) + 1 = 43\)
- \(p_5 = ((2 \cdot 3 \cdot 7 \cdot 43) + 1) \div 139 = 1807 \div 139 = 13\)
- \(p_6 = ((2 \cdot 3 \cdot 7 \cdot 43 \cdot 13) + 1) \div 443 = 53\)
- \(p_7 = ((2 \cdot 3 \cdot 7 \cdot 43 \cdot 13 \cdot 53) + 1 \div 248867 = 5\)
… after which, the series starts going crazy. The first fifty-one elements are known (http://oeis.org/A000945), but the next one is a factor of a 335-digit composite, and has not yet been calculated. Meanwhile, the lowest known prime not currently in the series is 41.
One interesting fact about the Euclid-Mullin sequence is, whether we start with 2, 3, 7, or 43, the first four values will be {2, 3, 7, 43} and the rest of the sequence will be the same. This is not true if we seed with 13. That is, starting with any of the first seven values of the basic sequence, we get these:
- (2, 3, 7, 43, 13, 53, 5, 6221671, …)
- (3, 2, 7, 43, 13, 53, 5, 6221671, …)
- (7, 2, 3, 43, 13, 53, 5, 6221671, …)
- (43, 2, 3, 7, 13, 53, 5, 6221671, …)
- (13, 2, 3, 79, 6163, 7, 1601, 11, …)
- (53, 2, 107, 3, 7, 11, 2620003, 707431, …)
- (5, 2, 11, 3, 331, 19, 199, 53, …)
Notice also that the second number in the series is always 2, except in the first case. This is easy to prove: All primes except 2 are odd, so \(p_1 + 1\) will be even except when \(p_1 = 2\).
Mullin also suggested a second sequence, \(q\), which consists of the greatest (rather than the least) prime factor. The basic sequence is:
- (2, 3, 7, 43, 139, 50,207, 340,999, 2,365,347,734,339, 4,680,225,641,471,129, 1,368,845,206,580,129, …)
Mullin created a few conjectural questions related to these sequences, the most significant being: Do either of these sequences ultimately include all primes?
It’s true that both sequences are infinite, since they rely on Euclid’s proof of infinite primes. But we know that there are different types of infinity. For instance, the set of even numbers is infinite, but it does not include any odd numbers. So it is possible that the Euclid-Mullin sequences do not create the full set of primes (and, furthermore, it’s possible that the two sequences don’t create identical sets).
Like Goldbach’s Conjecture*, Mullin’s basic conjectures are still open. However, while Goldbach’s Conjecture could ultimately be disproven through a counterexample, it’s not obvious how such a counterexample could appear for Mullin’s conjectures. It is known, for instance, that 41 does not appear in the first 51 elements of the first sequence, but that doesn’t mean that 41 doesn’t appear anywhere at all; since the sequences are infinite, it is impossible to create a definitive list of them. And Mullin’s sequences are not clearly predictable: The 48th element has 75 digits, while the next three are under 1000.
Incidentally, this is a case in which it’s useful for the empty product (that is, the product of the empty set) to be 1, which is the conventional definition. In such a case, \(p_0 = \emptyset \implies p_1 = 1 + 1 = 2\), which is what we want.
* Goldbach’s Conjecture: Every even number greater than 2 is the sum of two primes. Corollary: Every composite number is the average of two primes.