Prime time 01: An infinity of building blocks
Published: October 12, 2008Tags: number theory prime numbers primes mathematics
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 = 23 x 3 x 172,
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 = 710,
12345 = 3 x 5 x 823,
860552 = 23 x 7 x 112 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 p1, p2 and p3, we can still multiply them together in an infinite number of ways:p11 x p20 x p30,
p10 x p21 x p30,
p10 x p20 x p31,
p11 x p21 x p30,
p11 x p20 x p31,
p10 x p21 x p31,
p11 x p21 x p31,
p12 x p20 x p30,
p12 x p21 x p30,
p12 x p20 x p31,
...
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 p1, p2, ..., pn. 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 = p1 x p2 x ... x pn + 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 p1, ..., pn. So let's try to do that:We can't divide m by p1. That would leave us with:
m / p1= p2 x p3 x ... x pn + 1 / p1,
and 1 / p1 certainly isn't a whole number. We can't divide m by p2 either, as that would leave us with:m / p2 = p1 x p3 x ... x pn + 1 / p2,
and again 1 / p2 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 p1 through to pn 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.