Luke Maurits

Time for the second installment of my series on primes. This time I want to talk about the distribution of prime numbers: how primes are spread out along the line of positive integers. Are there any patterns in the distribution, or is it entirely random? This is a question which has concerned number theorists for centuries. Answers to questions about the distribution of primes can be surprisingly hard to find, and sometimes tantalisingly vague. There are a lot of results in this field of study. The canonical one is the aptly-named prime number theorem, but I’m going to simply gloss over this result at the end of the post. Instead I am going to focus mainly on two other ideas which aren’t as “powerful” as the prime number theorem, but are much more accessible to beginners.

Before I go any further, I’ll point out that the title of this entry, “the music of the primes”, isn’t my own creation, it’s the title of a famous book aimed at introducing some of the magic  of primes to the public at large. The phrase has since become common within the field.  I actually can’t guarantee that it originated with that book. At any rate, I borrowed it.

Twin primes, and beyond

One extreme in the distribution of primes is the existence of the so-called twin primes. The term twin primes refers to any two primes who differ by two, i.e. if p is a prime and p + 2 is a prime, the p and p + 2 are twin primes. There are a lot of examples of twin primes near the start of the positive integers: 5 and 7 are twin primes, as are 11 and 13 and 17 and 19. Twin primes are as close together as two primes can be: it is impossible for p and p + 1 to both be primes, since at least one of two consecutive
integers has to be even, and even numbers are, by definition, always divisible by 2. There is exactly one exception to this rule – 2 and 3 are consecutive and are both primes. This works because 2 is the only even prime number – which leads some mathematicians to jokingly call it “the odd” prime, a play on words using the alternate meaning of “odd” as “unusual”.  This says a lot about the sense of humor of a lot of mathematicians…

How many twin primes are there? As it turns out, nobody knows for certain. The twin prime conjecture states that there is an infinite number of twin primes. As the name suggests, this is a conjecture, not a theorem – it hasn’t been proven, although people have been trying to prove it for centuries. Certainly, most people who have studied the problem believe that the conjecture is true. With modern computers it’s relatively easy to search for twin primes automatically, and in this way number theorists
have found a lot of them. The largest pair of twin primes yet found is 2003663613 x 2¹⁹⁵⁰⁰⁰ – 1 and 2003663613 x 2¹⁹⁵⁰⁰⁰ + 1, two huge numbers with 58711 digits in them! The fact that as our computers get faster we keep finding higher and higher twin primes is just one reason to believe in the infinitude of twin primes (although it certainly isn’t a guarantee that we won’t one day stop finding them). There are a number of rough arguments based on known facts that make it feel more sensible that there are infinitely many twin primes than that there aren’t. Regardless of whether or not the twin prime conjecture is true, the fact is that there are a lot of twin primes out there: that is, there are a lot of cases where primes are distributed as close together as possible, which is an important consideration in trying to develop a feel for how the prime numbers are spread out.

Before moving on to the opposite extreme of prime distribution, I should point out that the idea of twin primes can be generalised pretty easily to prime triplets and various other higher level groupings. Some of these close groupings of primes are also conjectured to be infinitely abundant.

Large gaps in the primes

Having looked at the issue of twin primes, where primes are positioned as close together as they possibly can be, now I want to look at the opposite extreme: where the number line contains long stretches of non-primes (usually called “composites”) in between consecutive primes. There’s a really cool, kind of surprising and very easy to prove result about these situations, which simply says this:

For any positive integer n, there exist n consecutive integers, none of which are prime.

That is to say, you can pick any number you like – even the number of grains of sand on Earth or the number of stars in the universe, or any other outrageously large number – and it is guaranteed that somewhere along the number line there are that many non-prime integers in a row. The proof of this result doesn’t just establish that these prime-free stretches exist, it explicitly shows us how to construct them. This might sound obvious, but not all so-called “existence proofs” in mathematics are nice enough to come with instructions like this. Sometimes we prove something exists by assuming that it doesn’t and deriving a contradiction (the same logical strategy that we saw Euclid use to prove the infinitude of primes earlier), which doesn’t necessarily leave us with any idea how to find the thing we just proved the existence of. Maths can be funny like that. Anyway, this is one of the nicer cases where the proof shows us exactly where to look.

We need to sort out a tiny bit of notation first. When a mathematician puts an exclamation mark after an integer, like 42!, what they mean is the product of that integer, in this case 42, with every positive integer less than it, all the way down to one. So, for example:

5! = 5 x 4 x 3 x 2 x 1 = 120,

10! = 10 x 9 x 8 x 7 x 6 x 5 x 4 x 3 x 2 x 1 = 3628800

15! = 15 x 14 x 13 x 12 x 11 x 10 x 9 x 8 x 7 x 6 x 5 x 4 x 3 x 2 x 1 = 1307674368000

As you can see, these numbers get very large very quickly. By the way, when reading these equations out, the exclamation mark is pronounced “factorial”, i.e. 42! is “forty-two factorial”.  Now we’re ready to prove our result. Let’s say we want to find a prime-free gap of length 1000, i.e. 1000 non-prime numbers in a row. These numbers are simply:

1001! + 2, 1001! + 3, 1001! + 4, …, 1001! + 1001.

These numbers are clearly consecutive and there are also clearly 1000 of them. Are any of them prime? 1001! + 2 isn’t prime, because both sides of the addition sign are divisible by 2: 2 obviously is, and 1001! is divisible by any integer less than 1002, because it is, by definition, 1001 x 1000 x 999 x 998 x … x 2 x 1. So the first number in the sequence isn’t prime. 1001! + 3 also isn’t prime, because for the same reason both sides of the sum are divisible by 3. It should now be clear that all of the numbers in the sequence are divisible by something other than themselves, because of the way they are constructed. This isn’t a proof, yet, of course, it’s merely an example, but it’s very easy to generalise. To find n consecutive non-primes for any value of n, you just have to consider the sequence:

(n+1)! + 2, (n+1)! + 3, (n+1)! + 4, …, (n+1)! + (n+1).

So here we have a result that is at the opposite extreme of the conjectured infinitude of twin primes: there are an infinite number of cases where primes are spaced as far apart as you like.  In the interests of showing off some pedantic preciseness that being a good mathematician necessitates, I should point out that these theorem establishes that there exists at least one sequence of n consecutive composite numbers for any n. The sequence that is explicitly constructed in the proof is not guaranteed to be the only sequence of the length, nor the first such sequence to occur along the line. This isn’t really an important distinction for the purposes of demonstrating a contrast to the conjectured infinitude of twin primes, but it might be an important detail to keep in mind if we were to ever, say, use this result to attempt to prove another. But I’m digressing.

The big picture

So far we’ve only seen a kind of frustrating inconsistency in the distribution of the primes: sometimes we find them as close together as they can possibly get, and sometimes we find them so far apart that our minds can’t really grasp the significance of the number of composites between them. We haven’t seen yet anything on whereabouts these two phenomena happen along the number line or whether one happens more often than the other. The truth is that hard and fast rules about the distribution of primes are something modern mathematics is distinctly lacking. The more widely applicable a rule is, the more vague it seems to be. A sense of romance about this tantalising mix of apparent randomness and apparent order is what attracts a lot of people to the study of primes in the first place.

In the interests of completeness, having shown you some very specific results about the distribution of primes, I should talk about the prime number theorem, which is one of those results that says something kind of vague, but is more widely applicable.
The formal statement of the theorem that you’ll see on Wikipedia is not very accessible to non-mathematicians, so here’s a rough or, as a mathematician would say, “hand waving” statement that captures the gist of it:

As the positive integer n gets larger and larger, the chances of a random number picked from somewhere close by to n being prime gets closer and closer to 1 / ln(n).

Here ln(n) is the natural logarithm of n, which, to be very vague, is just something associated with a number than you can ask your calculator to figure out for you, much like the square root of n or the sine or cosine of n, etc.  This hand waving result can give us an intuitive sense for what happens to the distribution of primes as we get far out into the number line. If n = 100,000, then ln(n) is roughly 11.5, so about 1 in 12 numbers near 100,000 is prime. If n = 1,000,000, then ln(n) is roughly 13.8, so
about 1 in 14 numbers near 1,000,000 is prime. At n = 10,000,000 it’s 1 in 16 and at n = 100,000,000 it’s in in 18. If n is a googol (that is, a 1 followed by 100 zeros), about 1 in 230 numbers is prime. So we can see that prime numbers become more spread out the further we go along the line, but only in an “on average” sense of picking random numbers “near” some point on the line. The precise details of what is going on at any particular point are something a mystery until we actually crunch the numbers and look.

As a final point of interest, for those of you who get a lot more mileage out of a picture than a pile of words and theorems, here’s a graph showing the length of the gap between consecutive primes for the first 1000 such gaps. I got this data from the On-Line Encyclopedia of Integer Sequences (gaps between consecutive primes is sequence A001223). I drew the graph using gnuplot. At the very bottom left you can see a single red cross that is lower than every other cross on the graph: that represents the gap of 1 between the primes 2 and 3. There’s only one cross this low down because this is the only gap of 1 that ever happens in the sequence of primes, as we discussed 1earlier. All of the red crosses on the next level up represent gaps of 2: there is one cross for
every twin prime. The reason that the crosses appear to come in horizontal stripes is simply reflective of the fact that the gap between any two primes always has to be even (except in that one exceptional case of 2 and 3) – if you add an odd number to any prime other than 2 you get an even (and hence non-prime) number. At roughly n = 200 and n = 950 you can see unusually high crosses sitting above the crowd – hints at the fact we saw earlier that the gap between consecutive primes can actually
become arbitrarily large.

An (almost) 150 year old mystery

Although I’ve said all I really want to say on the distribution of primes for this entry, I would be remiss if I wrote something about the distribution of the primes and didn’t give at least a passing mention to something called the Riemann hypothesis. This is the grand daddy of unsolved problems in modern mathematics. No kidding. If you prove this hypothesis, first proposed in 1859 by Bernhard Riemann (a very important German mathematician who, amongst other things, developed mathematical ideas which later came to be important in Einstein’s theory of general relativity), to be true, you will win one million US dollars from the Clay Mathematics Institute (proving the Riemann hypothesis is one of seven so-called “millennium problems” that the CMI is offering a one million dollar reward each for) and serious fame. But don’t think this is easy money: the world’s very best mathematicians have been considering this problem for almost 150 years and nobody has found a proof yet. Aside 1from the simple attractiveness of solving a problem nobody else could in 150 years, one of reasons that so much effort is thrown at proving the Riemann hypothesis true is that if it is true, we’ll be able to use it to prove a lot of other interesting results. One of
these is a result similar to the prime number theorem but much stronger which would greatly improve our understanding of the distribution of prime numbers. This is some pretty heavy mathematics, and I freely admit that I don’t know enough about the connection between the Riemann hypothesis and prime distribution to talk intelligently about it here – but I know that is a very important connection and provides a lot of the motivation for actually working on the problem.

Like the twin prime conjecture, most mathematicians who have studied the Riemann hypothesis strongly suspect it is true – we just haven’t found a way to prove it beyond doubt yet.

Next prime time

Next prime time I want consider a slightly more practical issue about primes, namely: how do we actually know that a number is prime? This might sound silly, but when we are talking about the search for new primes larger than any found before, it is an entirely practical question to ask. We can’t take a candidate number n which might or might not be a new prime and then try dividing it by 2, then by 3, then by 4, and so until we’ve tried dividing it by everything up to n.  If n has 12978189 digits in it (like the current largest known prime) then trial division by every number less than n would take even the fastest computer on Earth an amount of time many orders of magnitude longer than our best estimates of the age of the universe. Thus we enter the field of
primality testing, which is all about clever tricks to test whether or not a number is prime as quickly as possible. Although the question this field tries to answer is conceptually simple, it turns out that the best known methods for efficient testing involve extremely advanced mathematics. I’ll introduce to one of the simplest improvements on trial division and discuss its strengths and weaknesses. Please look forward to it!

Time for the first entry in my promised series on primes. In this entry I hope to introduce prime numbers as the fundamental building blocks of integers (whole numbers for those of you who’ve been out of school for a while!), and then show how we know, beyond any doubt, that an infinite number of primes exists. Both of these results, or results very similar to them, are ancient, and have been either known or suspected for centuries. Despite this, they’re not things people ever seem to mention when they introduce someone to the concept of primality, which I think is a strong contributing factor to why few people understand the intense sense of interest and reverence that mathematicians seem to bestow upon the primes.

Primes as building blocks

So, what do I mean when I speak of primes as building blocks? I am referring to a result known to number theorists as the fundamental theorem of arithmetic, which states this:

Every positive integer greater than 1 can be uniquely written as a product of prime powers.

For example, we can write the number 6936 in the form:

6936 = 2³ x 3 x 17²,

which is special in the sense that 2, 3 and 17 are all primes – we’ve expressed 6936 as a product of prime powers. This way of writing a number is usually called its “canonical factorisation”. Here are a few more examples of canonical factorisations:

282475249 = 7¹⁰,

12345 = 3 x 5 x 823,

860552 = 2³ x 7 x 11² x 127.

There are two aspects to this theorem – the fact that such a representation exists for every integer, and the fact that it is unique, i.e. there is only one such representation for every integer. I won’t discuss the rigorous proof of either aspect here as I don’t think the details are sufficiently enlightening to impose the burden of pedantic detail on readers who are not mathematicians (later in this post I will go though a proof where I think this trade off is more than fair). But it is easy enough to develop an intuitive understanding of why the first aspect is true: if a number is itself a prime then the canonical factorisation of that number is just that number itself, and we’re done. If a number isn’t prime then by definition it is divisible by something else, in which case we can write it as a product of two other numbers. If those other two numbers are both prime then we’ve arrived at a canonical factorisation. If they aren’t, then once again by definition we must be able to split them up further. Recursive application of this simple principle eventually leaves us with a product of primes, which constitutes the kind of factorisation we’re looking for.

In light of the fundamental theorem of arithmetic, it makes sense to say that prime numbers are building blocks for the integers – every integer is made from a finite number of primes multiplied together. With this in mind, it is entirely natural for number theorists to make primes an important object of study – just as natural as it is for biologists to study cells as the building blocks of living organisms, or for chemists to study atoms as the building blocks of molecules. In the same way that an understanding of cells or atoms can lead to a better understanding of biological processes or chemical reactions, sometimes it is possible to answer a question about a particular number by first breaking it into its prime components and then answering the question about each prime component individually.

Hopefully it is now clear that the property of being prime is in no way an arbitrary numerical curiosity like being perfect.  There is a combination of theoretical fundamentality and practical usefulness in primality that makes it entirely deserving of close attention and careful consideration.

The infinitude of primes

Having established the importance of primes as building blocks of all other integers, a natural matter of concern is the question: “How many primes are there?”. It may be tempting to suggest that there “obviously” has to be an infinite number of primes to account for the fact that there are obviously an infinite number of integers. But this is not the case. A finite set of primes would be sufficient to generate an infinite amount of integers, since there is an infinite number of integers from which to select powers. If there were only 3 primes in existence, let’s call them p₁, p₂ and p₃, we can still multiply them together in an infinite number of ways:

p₁¹ x p₂⁰ x p₃⁰,

p₁⁰ x p₂¹ x p₃⁰,

p₁⁰ x p₂⁰ x p₃¹,

p₁¹ x p₂¹ x p₃⁰,

p₁¹ x p₂⁰ x p₃¹,

p₁⁰ x p₂¹ x p₃¹,

p₁¹ x p₂¹ x p₃¹,

p₁² x p₂⁰ x p₃⁰,

p₁² x p₂¹ x p₃⁰,

p₁² x p₂⁰ x p₃¹,

…

It is (hopefully!) clear that we need never stop – we may continue raising our mere three primes to arbitrary choices of arbitrarily high integer powers. So there is some substance to the question after all: is it possible that after, say, one million primes, the set of possible integers you can make by multiplying together different powers of primes actually encompasses every integer?

It turns out that there are, in fact, an infinite number of primes, but I feel it is important to establish that this is not obvious, as I have had people tell me it is in the past.  The proof that there is an infinite number of primes is attributed to the ancient Greek mathematician Euclid, and it is in my opinion one of the most important proofs that a non-mathematician can be shown. It is elegantly simple, demonstrates a method of reasoning known as reductio ad absurdum which is extremely powerful and is used everywhere in mathematics, and offers a glimpse at the kind of thinking that mathematicians actually do, which is almost nothing at all like what most non-mathematicians think it is.

The proof starts by assuming that there is a finite number of primes. We don’t need to specify an exact number, it just needs to be less than infinity. We’ll call it “n” so we can refer to it as something. If this makes you uncomfortable, you can mentally
replace n by 42,000,000 everywhere after this point, it won’t change the details. What’s important is that based on this assumption we’re going to logically derive something that contradicts the assumption. We’ll see exactly what that means for our assumption later.   Let’s continue…

So, we have n primes, let’s call them p₁, p₂, …, p_n. We can multiply all of these primes together and then add 1 to the result to get a new number, which we’ll call m:

m = p₁ x p₂ x … x p_n + 1

Let’s think a bit about m, specifically about what we can divide it by. Remember that the fundamental theorem of arithmetic says that we can write m, just like any other integer, as a product of prime powers. That means that we should be able to divide m by one of our primes p₁, …, p_n. So let’s try to do that:

We can’t divide m by p₁. That would leave us with:

m / p₁= p₂ x p₃ x … x p_n + 1 / p₁,

and 1 / p₁ certainly isn’t a whole number. We can’t divide m by p₂ either, as that would leave us with:

m / p₂ = p₁ x p₃ x … x p_n + 1 / p₂,

and again 1 / p₂ isn’t a whole number. In fact, it should now be clear that m has been cleverly constructed so that it cannot be divided by any of the n primes in our set. Which, since the fundamental theorem of arighmetic is true (I know I did not prove
this earlier, but hopefully gave you sufficient grounds on which to trust me!), means that there must be some other prime number out there, missing from our set, which divides m. But we started with the explicit assumption that p₁ through to p_n comprised the entire, finite set of primes. We have contradicted ourselves!

What does this mean? We’ve shown that assuming that only a finite number of primes exist (any finite number of primes – see how the actual value of n played no important role in getting to this point?) leads directly to a logical inconsistency. The entire point of mathematics is that things should be consistent. Any assumption which leads to inconsistency has to be wrong and so we reject it. This is a general technique that mathematicians use often to decide whether or not something is true: if by assuming something is true you can use logical steps in thinking to “prove” something you know is false (or, equivalently, to contradict something you know to be true), then that initial something you assumed must be false, to preserve the consistency of mathematics as a whole. In this particular case, the initial assumption was that there are only a finite number of primes, and based on this assumption we were able to contradict something that followed from the known truth of the fundamental theorem
of arithmetic. Thus we are forced to reject our original supposition, which leads to our goal: certainty that there must be infinitely many primes.

If you’ve followed this argument for why there must be an infinite number of primes, you shouldn’t discount the significance of that achievement! This very line of thinking dates back to at least 300 years BC, and the very same logical steps have been followed through by countless people in every country of the world ever since then. This may be one of the most often-shared abstract mental experiences of the human race! It also provides an excellent first glimpse into the world of pure mathematics, which has no concern whatsoever with actually performing computations or solving equations or doing any of the other things you probably remember maths being all about in school. Instead its all about figuring out universal truths about numbers (and other things), like the fundamental theorem of arithmetic, or answering tricky questions with certainty, not by relying upon particular examples or special cases or gut instinct, but by using clever logical arguments, like Euclid’s argument for the infinitude
of primes.

Next prime time

Now that we have some appreciation for why primes are interesting, and know that there are infinitely many of them out there, I’ll use the next Prime Time entry to discuss what feels like the next natural question: where do we find the primes? Is there a pattern in the way they are spread out through the integers? Are they sprinkled about evenly? Are they bunched up toward the low numbers, or are they bunched up out somewhere near infinity? Are they distributed completely randomly, with no rhyme or reason? Questions like these and their sometimes surprising answers are a source of a lot of the sense of mystery and captivation that a lot of people feel about primes. Please look forward to it!

As was reported at various places (see, e.g., the BBC), in August this year a prime number (in particular a Mersenne prime) was discovered which was larger than any previously known prime – the first 10 million digit prime number! The number, 2^43112609-1, was discovered by a distributed computing project called GIMPS, the Great Internet Mersenne Prime Search. Congratulations to everyone involved!

I have been wanting for a while now to introduce more non-programming related content to this blog and the discovery of this new prime has motivated me to write somewhat regularly about issues in number theory and about prime numbers and related concepts especially. I think prime numbers are very misunderstood, or perhaps it would be better to say “under-understood”. Almost everybody understands what a prime number is, but very rarely is anybody ever told why it is that mathematicians get excited by them. The BBC story linked to above, for example, offers not even a token explanation as to why millions of people donate their spare computer power to a world-wide collaborative effort to find large new primes, or why organisations like the EFF are willing to offer large cash prizes for people who find primes. Do prime numbers actually have practical uses? Yes! Are there good intellectual reasons to be more interested in them than all the other, composite numbers? Yes! Is there something special and enchanting about primes that causes people to become obsessed with trying to understand them? Yes! But it’s an exceedingly rare school teacher who mentions any of these things when teaching kids what a prime number is. To be fair, perhaps that in particular isn’t unreasonable – in Australia, at least, children are taught what a prime number is at a fairly young age, too young to really appreciate many of these things. Perhaps the problem is that primes, and number theory in general, aren’t ever revisited later in a child’s education, where these things could be made clear.

I have personally fallen “victim” to this. Until I switched from a physics to a mathematics major in university, I had no idea why anybody would particularly care about prime numbers. I thought that the division of numbers into primes and composites was no more compelling than the division of numbers into odd numbers and even numbers, into perfect numbers and imperfect numbers, into triangular, square, etc. numbers. Many of these distinctions struck me as rather arbitrary and uninteresting ones, based on frankly quite childish and superficial observations. I still hold this opinion today for most of these divisions, but I have learned a lot about primes (and their abstract algebraic generalisations!) since then and now understand that they certainly do not belong in the same mental pigeon hole as perfect or square numbers.

In an attempt to help spread some of this understanding, over the next few months I’ll try to write entries explaining some of the reasons prime numbers are interesting, some of their practical applications, explain some simple algorithms to do with prime related concepts (like primality testing and factorisation) and point out some of the many compelling mysteries about primes that continue to capture the attention of mathematicians today. A survey of interesting stuff to do with primes will take readers all the way from ancient Greece, around 300 BC, to the early internet days of the 1970s and 1980s, with a few detours through 17th century France. I’ll try my best to make the material interesting and accessible to non-mathematicians. Please look forward to it!