Prime Numbers: A Thousand Year-Old Puzzle

Many of us are familiar with the concept of prime numbers: natural numbers greater than 1 that are not a product of two smaller natural numbers. Listing out the first several prime numbers gives us: 2, 3, 5, 7, 11, 13, 17,... Though their definition is rather straight forward, prime numbers are a lot more puzzling than one might think, which is why mathematicians find them so fascinating.

As you might have already observed, the sequence of prime numbers possesses no regularity whatsoever, rendering it extremely difficult for mathematicians to analyse. If we take, for example, a series of odd numbers (1, 3, 5, 7, 9, 11,...) or consecutive square numbers (1, 4, 9, 16, 25, 36,...) there is a clear, methodical approach to getting from one number to the next. When it comes to prime numbers, there is no such thing. In fact, they tend to appear almost randomly across the counting numbers.

The Fundamental Theorem of Arithmetic

The Fundamental Theorem of Arithmetic goes as follows: Any integer greater than 1 is either a prime number, or can be written as a unique product of prime numbers. For example 6 = 2 × 3. Any number that can be written as the product of two or more prime numbers is called composite.

This theorem is also the reason why there is 60 minutes in an hour and 360 degrees in a circle. These numbers were chosen because they are made up by many prime factors.

Prime factorisation of 360 gives us 2, 3 & 5 with the same results for the prime factorisation of 60.

What Makes Them So Tiresome?

Over the last 2500 years, mathematicians have made very little progress in locating and predicting the location of prime numbers within the sequence of natural numbers. Want to see why? Take a look at the differences between the prime numbers (2,3,5,7,11,13,17,19,23...): 1,2,2,4,2,4,2,6... and though they vaguely seem to be getting bigger, they are so sporadic that there is ultimately no way of predicting what the next difference will be.

The proof for this goes as follows:

The sequence between gaps between consecutive prime numbers, starting from the first gap (g1)...

(The first prime number (2) subtracted from the second prime number (3) which gives us 1, also denoted as g1)

... cannot be split into subsequences such that repetitions of this subsequence cover all prime gaps. Or when expressed numerically:

We can use proof by contradiction to deny this theory.

First, we must enumerate the prime numbers to get:

And the corresponding gaps where gn = Pn+1 - Pn can be written as

If this sequence of gaps repeated for some finite n>0. Then

Adding the sequence of gaps together, we have a sum of Ln

which we can be certain is integer, and thus can either be even or odd. If Ln is even, prime pn must also be even because pn = 2+Ln. But if Ln is odd, then P2n = 2+2(Ln) = 2(1+Ln) therefore p2n is even. However, this is a contradiction because the only even prime number is 2. Therefore the sequence of gaps between consecutive prime numbers cannot repeat itself no matter how large n is, which can lead us to conclude that all subsequences of g1, g2, g3, ... are aperiodic.

So, if the differences between consecutive prime numbers are so sporadic, how can we be sure that there are an infinite number of them?

Euclid's Proof of the Infinitude of Primes

Euclid's theorem is a fundamental statement in number theory asserting that there are an infinitude of prime numbers. It was first proven by Euclid in his work Elements, and today, there exists several proofs of the theorem.

If you consider any finite list of prime numbers p1, p2, ..., pn. We will try to prove that there exists at least one additional prime not included in this list, that is to say, one prime number after pn. Let P be the product of all the prime numbers in the list:

P = p1 × p2 × p3 × ... × pn.

Let q = P + 1, where q is either prime or not.

This will lead us to two solutions:

1. If q is a prime, there there is at least one more prime that is not on the list.
2. If q is not prime, then it is divisible by some prime factor p. If this factor p were in our list it would divide P (since we have established that P is the product of every number in the list); however, p also divides P + 1 = q. So if p divides P and q, then p must also divide q - P, which is (P + 1) - P, or just 1. Since no prime number divides 1, p cannot be in the list. Which means that q is a prime number, which leads us to conclude that there is at least one more primer number beyond those in the list.

This theorem proves that for every finite set of prime numbers, there is a prime number not in the list, and therefore, an infinite set of prime numbers.

So now that we have established that there are an infinite number of primes, is there a methodical way of finding all of them?

The Sieve of Eratosthenes

Eratosthenes was a Greek mathematician who wanted to prove, no matter how tedious the method, whether any given number is a prime or composite.

To do this, he constructed an algorithm for finding all prime numbers up to any given limit (n).

Let us say that the input is 100, so n=100, meaning that we need to find all prime numbers smaller than or equal to 100. To clearly visualise this, we can create a list of all numbers from 2 to 100.

According to Eratosthenes' reasoning, we must mark all the numbers which are divisible by 2 and are greater than or equal to the square of it (this is because these numbers are composite.)

The next integer on the list that is not marked out is 3, and it is prime. Mark out all multiples of 3 that are bigger than 3 because they are composite.

The next integer on the list that is not marked out is 5, and it is prime. Mark out all multiples of 5 that are bigger than 5 because they are composite.

We continue this process for all of the unmarked numbers until the final table looks like this:

So the unmarked numbers: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89 and 97 are prime numbers.

Surprisingly, not much progress had been made since Eratosthenes' time. We still use the exact same method to test a number. We divide it by every prime number less than or equal to its square root to see if we can do so cleanly with no remainder. If every single prime number we divide it by leaves a non-zero remainder, the number is prime.

Now that we have learned this neat trick to determine whether a number is a prime, what other methods are present-day mathematicians working on?

Contemporary Advancements

The Great Internet Mersenne Prime Search (GIMPS) is a collaborative project of volunteers who use freely available software to search for Mersenne prime numbers. It was founded in 1996 by George Woltman and is said to be one of the first large scale volunteer computing project over the Internet for research purposes.

As of October 2022, the project has found a total of seventeen Mersenne primes; fifteen of which were the largest known prime number at their times of their discovery. The largest known prime as of September 2022 is 2^82,589,933 − 1 (or M_82,589,933 for short) and was discovered on December 7, 2018, by Patrick Laroche.

To find these primes, the project relied on the Lucas-Lehmer primality test which is an algorithm that specializes in testing Mersenne primes with maximum efficiency on binary computer architectures. However, in 2018, GIMPS adopted a Fermat primality test as alternative, more favoured option for primality testing, still using the Lucas-Lehmer test as a double-check for Mersenne numbers detected as probable primes by the Fermat test.

The Lucas-Lehmer test is deterministic, while the Fermat test is probabilistic. However, the likelihood of the Fermat test identifying a Fermat pseudoprime that is not actually prime is far lower than the error rate of the Lucas-Lehmer test, which can be affected by hardware errors.

In September 2020, GIMPS began supporting primality proofs based on verifiable delay functions. These proof files are generated during the Fermat primality test. Along with an error-checking algorithm developed by Robert Gerbicz, these methods ensure complete confidence in the test results, eliminating the need for double-checking. As a result, first-time Lucas-Lehmer tests were phased out in April 2021.

Conclusion

This article barely covered the tip of the iceberg when it comes to prime numbers. For centuries they have fascinated mathematicians, their surface-level simplicity giving way to the tremendous difficulty of analyzing them at depth.

It still amazes me how the very building blocks of number theory can be so puzzling to us, even after all these years of trying to piece "the puzzle" together. Could it be another one of those unexplainable phenomenons of the universe? A problem that will never be solved?

Only time will tell. But until then, look forward to future articles about the intricacies of prime numbers.