For mathematicians, prime numbers are special. Values that are only evenly divisible by themselves and one, they can be combined through either addition or multiplication to produce every positive integer greater than two, which makes them the building blocks of the set of all whole numbers.
But if you search for prime numbers, you'll find they're not evenly distributed among all those positive integers. While they are really dense at the low end of the positive number line, they thin out and appear less and less frequently as the count of numbers grows ever higher.
That leads to a natural question. If you count high enough, will you run out of prime numbers to discover?
Mathematicians are happy to confirm the answer to that question is no. There's always another larger prime number to be found!
They can confirm that characteristic of prime numbers with certainty thanks to one of the world's oldest mathematical proofs that was documented by the Greek mathematician Euclid around 2,300 years ago. James Grime talks through Euclid's proof in the following seven minute Numberphile video, in which the trick is to assume you can produce a list that contains all prime numbers, then prove that assumption is wrong:
Euclid's logic confirming prime numbers extend into infinity is an example of a proof by contradiction. It's a twisty-turny way of thinking, but one that works.
Here's something else that's neat about the prime numbers of Euclid's proof. If you remember that grid of numbers illustrating patterns of primes we introduced a while back, you'll always find prime numbers that satisfy Euclid's logic in the Set F column of the table.
For example, if we make a set of primes using just the first two in the table, the values 2 and 3, multiplying them together produces 6. Adding 1 to that value gives us 7, which is our first Euclid Set F prime number result if we treat Euclid's proof like an algorithm.
Let's take that algorithm one step further and include the third prime, 5, in the set of primes. Multiplying 2, 3, and 5 together results in a product of 30. Add 1 to that product, and we find 31 is our second Euclid Set F prime.
If we expand the list of primes to include 2, 3, 5, and 7, we find their product is 210 after multiplying them together. Adding 1, we reach the end of the presented table with our third Euclid Set F prime, 211.
We could continue, but since we've exceeded the listed values of the table, let's talk about why that works!
In the table, Set F values are always the result of taking a multiple of 6 and adding 1 to it. The way the table is set up, you can take the value 6, multiply it by the row number (ROW), and add 1 to produce the results shown in the Set F column.
Set F Value = 6*ROW + 1
Euclid's proof is doing identical math! The product of the first two prime numbers, P₁ (2) and P₃ (3), is 6, so we can extract them from the rest of the prime number multiplications:
Q = P₁*P₂*P₃*...*Pₙ + 1
Q = (P₁*P₂)*(P₃*...*Pₙ) + 1
Q = (2*3)*(P₃*...*Pₙ) + 1
Q = 6*(P₃*...*Pₙ) + 1
In this formulation, the product of the prime numbers P₃ through Pₙ is equivalent to the row number of the table. Recognizing that equivalence, we get:
Q = 6*ROW + 1
Where the Euclid prime Q will therefore always be a Set F value from the table. Specifically, they're the ones that correspond to the row numbers that are the cumulative products of prime numbers greater than 3.
Meanwhile, the largest confirmed prime numbers, which belong to the Mersenne family of prime numbers, are also all Set F primes, but that's a different discussion for another day....
References
Ansh Pincha. The Infinitude of Primes — Euclid’s proof. Quantaphy. [Online Article. 13 August 2023.
Chris K. Caldwell. Euclid's Proof of the Infinitude of Primes (c. 300 BC). PrimePages. [Online Article]. 2021.
Chris K. Caldwell. Proofs that there are infinitely many primes. PrimePages. [Online Article]. 2021.
Euclid. Proposition 20. Elements, Book IX. Circa 300 B.C.
Image credit: Photo of Prime Tower in Zurich, Switzerland by Claudio Schwarz on Unsplash.