Infinite Wonders: The Journey and Factory of Prime Numbers

The factory of prime numbers

Ancient Origins

The ancient Greeks, driven by a passion for knowledge and mathematical beauty, gave the world its first formal glimpse into the realm of prime numbers. Euclid, through his legendary "Elements," provided definitions and theorems that remain foundational to this day.

Yet, whispers of primes can be traced back even earlier, in the ancient scrolls of Egypt, Babylon, and China, where the seeds of mathematical discovery were first sown. The journey of prime numbers is a tale of human curiosity, brilliance, and the eternal quest to understand the fabric of our numerical universe.

Basic Concepts

We consider only positive integers: 1, 2, 3, and so on. There are infinitely many of them. If $n$ is an integer, however large, we can always add 1 to $n$ to get $n+1$, which is even larger.

If $m$ and $n$ are two integers, we write $m\mathrm{\mid }\mathrm{n\; if }$$m$ divides $n$. This means $n$ is an integer multiple of $m$. For instance, it is true that $2\mathrm{\mid }4$ but not true that $2\mathrm{\mid }5$.

Prime Numbers

Of course, number 1 is a trivial (non-interesting) divisor of every integer. It is also true that for every integer $n$, we have  $n\mathrm{\mid }n$.

Prime numbers are characterized by the fact that they do not have any other divisors except the trivial ones: 1 and themselves.

There is an interesting fact that we will use below. Take two consecutive integers $n$ and $n+\mathrm{1.\; They\; never\; have\; a\; common\; non-trivial\; divisor.\; Indeed,\; suppose\; an\; integer }$$p$ greater than 1 divides both $n$ and $n+1$. Then it would also divide the difference $(n+1)\text{–}n$. But this difference is 1. No number greater than 1 divides 1. End of proof.

Euclid's Fundamental Theorem of Arithmetic

We also need Euclid's Fundamental Theorem of Arithmetic [1, p. 26]:

Every positive integer can be written uniquely (up to order) as the product of prime numbers.

Here, one may wonder about the number 1. 1 certainly a positive integer. There are two ways to address this. One way is to restrict positive integers to those greater than 1, as we did in the beginning. The other way is more tricky. In mathematics, the product of numbers in the empty set is considered, by a convenient definition, to equal 1. So, 1 is the product of an empty set of primes!

Building the Prime Number Factory

It is time now to build our factory of prime numbers based on the old idea in Euclid's "Elements" (circa 300 BC). The fact that such a factory exists means that the number of primes is infinite, thus there is no such thing as the Last Prime Number. The factory's principle is this: for any finite collection of prime numbers, it constructs another prime number, which was not in the collection. We can add this number to get an even bigger collection and run our machine again. Ad infinitum. Here's how it works:

Euclid's Prime Numbers Producing Machine

Let $a,b,c,\dots ,k$ be any (finite, non-empty) collection of prime numbers. Take their product $P=abc\dots k$. Add 1 to $P$ to get $P+1$. Then $P$ and $P+1$ are consecutive integers. Therefore, they do not have common non-trivial divisors. Now, there are two possibilities: either $P+1$ is a prime number, or it can be divided by some prime number $p$. If it is a prime number, then this prime number is certainly bigger than any of the numbers $a,b,\dots ,k$. So we add it to our collection and get a larger collection. If $P+1$ is not a prime number, it is divisible by a prime number $\mathrm{p\; and}$ then $p$ cannot be in our previous collection because $P$ and $P+1$ have no common non-trivial divisor. We add $p$ to our collection and get a larger collection. End of proof.

Remark: If P is greater than 2, which is always the case with only one exception: when our original collection is just {2}, then,  of course, we can replace in the machine going from $P$ to $P+1$ by $\mathrm{going\; from\; P\; to\; P}-\mathrm{1,\; since }$$P-\mathrm{1\; and }$$P$ are also consecutive integers. 

An Example of the Machine in Action

Let us see how the machine works on an example (cf. [2,3]). Let's start with the following pair of prime numbers {5, 11}.

Then $P=55$. Take $P-1=54$. It is not a prime number. It has prime divisors 2 and 3. We add them to our collection to get {2, 3, 5, 11}. We multiply them to get a new $P=330$. We subtract 1 to get 329. Again, it is not a prime number, but it is a product of two prime numbers 7 and 47. We add them to our collection, which becomes now {2, 3, 5, 7, 11, 47}.

We multiply them to get a new $P$, this time $P=108570$. Again, we subtract 1 to get $P-1=108569$. Again, it is not a prime number, but it is a product of two prime numbers 151 and 719. We add them to our collection to get {2, 3, 5, 7, 11, 47, 151, 719}.

These were just a few steps, but the machine can work till the end of time, producing at each step new prime numbers. There is no “Last Prime Number.”

Remark: If P+1 is not a prime number, we can add to the collection not just one of its prime divisors, but all of them that are different from each other.

Remark: The machine is of course not very effective as it requires factorization of larger and larger numbers. But it does its job, which is:  of proving the infinity of primes. 

Exercise: Start just with {2} instead of (2,3,5}. Use the algorithm above. Describe what happens.

The Mysteries of Primes

The infinitude of primes has its mysteries. Mathematicians are always on the lookout for patterns and regularities in prime numbers. Recently, researchers from City University of Hong Kong and North Carolina State University released a paper entitled “Periodic Table of Primes" [4]. They argue that primes can be predicted using a periodic table-like structure. The date of appearance of this paper (April 6, 2024) differs only by the prime number 5 from April 1, which brings to mind some prime associations.

Summary

Prime numbers, those elusive building blocks of mathematics, have captivated minds from ancient Egypt to modern academia. With Euclid's timeless machine, we've shown that the hunt for primes is a never-ending adventure. As mathematicians continue to unravel their mysteries, who knows what prime secrets await discovery? So, next time you ponder numbers, remember: there's always another prime just around the corner. Happy number crunching!

References

[1] Melvyn B. Nathanson, Elementary Methods in Number Theory, Springer, 2000.

[2] M. Hardy, C. Woodgold, Prime Simplicity. Math Intelligencer 31, 44–52 (2009). https://doi.org/10.1007/s00283-009-9064-8

[3] M Hardy, Notes 98.20 A concrete view of Euclid’s proof of the infinitude of primes, The Mathematical Gazette, volume 98, issue 543 (2014), https://doi.org/10.1017/s0025557200008172.

[4] Han-Lin Li, Shu-Cherng Fang, Way Kuo, The Periodic Table of Primes, Date Written: April 6, 2024, https://doi.org/10.2139/ssrn.4742238.