Why are primes considered to be the "building blocks" of the integers?

Question

I watched the video of Terence Tao on Stephen Colbert the other day (here), and he stated, like many mathematicians do, that the primes are the building blocks of the integers.

I've always had trouble with this idea, because I don't think it's a philosophically sound idea.

I'm going to start by stating the basic argument: An integer can either be expressed as a product of smaller integers or not. If not, it's called "prime".

But you could say the same thing about powers: An integer can be expressed as a (well, I'm not a mathematician and now I'm at a loss for words) power-chain of integers or not. If not, it's called (I don't know what the name could be) "power-prime". For example, 16 = 2^2^2, so it's power-composite, whereas 2 can't be expressed with powers, so is power-prime.

Again, you could say the same thing about addition: An integer can be expressed as a sum of integers or not. If it can, it's called an integer. If not, it's called "unit", I guess, because every integer can be expressed as a sum of 1's! So, truly, the unit is the building block of the integers.

So, I don't think there's any truth in the idea that the primes are the building blocks of the integers. I think it's just an expression of a human preference for multiplication because multiplication is complicated enough to be interesting to us (unlike addition), but not so complicated that it's bewildering (like powers). Or maybe because the notation we use to express powers doesn't use an explicit operator, nobody has noticed that you can treat powers analogously to multiplication in a situation like this. Just a couple of theories.

I'd be curious to know what research has been done in this area. I bet the power-primes have a lot of interesting properties.

Further clarification of what I mean by "power-prime":

I'm just talking about factoring integers using the exponentiation operator rather than the multiplication operator.

I apologize for using the ugly term "power-prime", but I don't know what these are officially called. I don't even know what to call a bunch of numbers that are combined by exponentiation! A bunch of numbers combined by addition is called a "sum". Numbers combined by multiplication is called a "product". What is the term for a number of numbers combined by exponentiation? I'm having a major memory lapse because I feel I should know what it is.

I'll make a table because examples are easiest to understand. I'm going to use the caret ^ character for exponentiation (2^2 = $2^2$).

n   factoring  name
1
2              p-prime
3              p-prime
4   2^2        p-composite
5              p-prime
6              p-prime
7              p-prime
8   2^3        p-composite
9   3^2        p-composite
10             p-prime
11             p-prime
12             p-prime
13             p-prime
14             p-prime
15             p-prime
16  2^2^2      p-composite
17             p-prime
18             p-prime
19             p-prime
20             p-prime
21             p-prime
22             p-prime
23             p-prime
24             p-prime
25  5^2        p-composite
26             p-prime
27  3^3        p-composite
28             p-prime
29             p-prime
30             p-prime
31             p-prime
32  2^5        p-composite

See, every natural number is either p-prime or a combination of p-primes (via exponentiation). I don't know if each of these factorings is unique, since, as was mentioned by Pete, it's highly non-obvious. I honestly don't think that Fundamental Theorem of Arithmetic helps here because exponentiation is not commutative, but I could be wrong. It's also noteworthy that our usual exponentiation operator is right-associative. A left-associative exponent would give a slightly different table, since for example (2^2)^3 $\ne$ 2^(2^3).

Answer 1

It's good that you asked the question. A complete answer will take several steps (many of which others have given, but are important enough to repeat).

1. There is something fundamentally wrong-headed about describing the statement that the primes are the building blocks of the integers as "philosophically unsound". To be philosophically unsound, something must be philosophical. But Tao's soundbite is a standard shorthand for a mathematical fact.

2. You say the basic argument is

An integer can either be expressed as a product of smaller integers or not. If not, it's called "prime".

Then you point out that this itself is not a very exciting fact or very special to the primes: one can make similar statements for the powering operation and for lots of other things. Your second observation is absolutely correct. But what you called the "basic argument" is not at all the statement in question. It is not in fact an argument at all: it is just the definition of a prime number (among integers greater than $1$). The statement that the "building blocks" refers to is much more profound and comes in two parts:

Part I: Every integer greater than $1$ can be expressed as a product of prime numbers: that is, for all $n > 1$, there are prime numbers $p_1,\ldots,p_k$ such that $n = p_1 \cdots p_k$. (Note that we allow "products" in which $k = 1$: these are precisely the prime numbers. This point sometimes confuses beginners.)

Part II: The factorization into primes is unique in the following sense: if we write

$n = p_1 \cdots p_k = q_1 \cdots q_l$

where $p_1 \leq p_2 \leq \ldots \leq p_k$ are primes (taken in increasing order) and $q_1 \leq \ldots \leq q_l$ are primes (also taken in increasing order) then $k = l$ (i.e., the number of factors, or blocks, is the same) and $p_1 = q_1$, $p_2 = q_2$, all the way up to $p_k = q_k$.

Taken together, Parts I and II are called the Fundamental Theorem of Arithmetic, and this is the argument in question.

As an aside, let me note that with the usual goodwill we extend to the infinite set of natural numbers, Part I is almost obvious: you take $n > 1$. If it's not prime, then by definition you can write it as $n = ab$ with $a,b < n$. If $a$ and $b$ are not prime, you repeat. After every step the largest factor gets smaller, so certainly this process terminates eventually: that's Part I.

Part II is highly nonobvious: it was first (essentially) proved by Euclid, and in a university-level course in which students had not seen this material before I would probably spend two full lectures on the proof. The fact that it seems like it should be obvious is a piece of psychology that one has to get past in one's study of this subject. (Why? Because in fact there are many other natural contexts in which one wants closely analogous results to be true and they're not! In the mid 19th century, the French mathematician Gabriel Lamé thought he had proven Fermat's Last Theorem because of a mistake like this!!)

Do you see why Parts I and II together can be well paraphrased by saying that the primes are the building blocks for the integers (again, let's say integers greater than $1$)? Think of each prime as being a kind of block: picture maybe an actual block which has the number written on each face. We have an infinite supply of each kind of block -- imagine a bin receding out into the distance with "2 blocks", another one with "3 blocks" and -- well, there are a lot of blocks and bins. Then to "build" just means to take finitely many blocks altogether from the bins: you can take more than one block from any given bin. Then you take the blocks and multiply them together to get a number. Every number can be built that way: Part I. More profoundly, if you show me your final number then -- given enough time! -- I can deduce exactly what your blocks are. For this imagine that you have built something incredibly complicated out of a bunch of legos that are all the same color. From far away it's not clear at all what legos you used. But once I start removing legos -- factoring! -- then eventually I will of course end up with exactly the same number of legos of any given shape and size as you did. (Perhaps this analogy is bad in the sense that it makes Part II look obvious. But I think it helps in understanding the statement, so I won't mess with it.)

3. It would be more precise to say that the primes are the multiplicative building blocks of the integers: the building operation is multiplication, and after all there is another operation in play as you perceptively point out. In this sense, their role is absolutely special: they are the single blocks. If you want to change the operation then the statement certainly does not apply.

So let's change the operation...to addition. Now we had better include $1$, because that's our building block. In fact, in contrast to the multiplicative situation in which there are (thanks to Euclid again) infinitely many building blocks, in the additive situation there's just one block, the number $1$, and of course we get any positive integer $n$ by adding $1$ to itself $n$ times. This is true and important...but obviously much less interesting than the multiplicative situation (I got a flashback to the joke 1980's videogame "Quayletris"), so you can perhaps forgive mathematicians for omitting the word "multiplicative". In fact there is a mathematical sense in which the multiplicative structure is obtained from "infinitely many copies" of the additive structure. This is presented formally in problem G1 from the first problem set of my number theory course. Note though that the G stands for "graduate level": if you do not have some training with abstract mathematics, I am afraid it might not make much sense.

Finally, what makes the integers interesting is precisely the fact that we have both additive and multiplicative building blocks. Taking each separately on its own terms we have a completely transparent structure. But when we start mixing the two, we get tough questions alarmingly quickly. Take a prime number $p > 2$. Is $p -1$ prime? No, it's even. Okay, is $\frac{p-1}{2}$ prime? Not necessarily, but in plenty of examples. Infinitely many times? Yikes: we don't know. Okay, take $p> 3$. Is $p-2$ prime? Not necessarily, but in plenty of examples. Infinitely many times? Yikes: we don't know. Well, in the latter case we know tremendously more now than we did two years ago, but that's another story.

Added: I read the end of your question more carefully, and you do indeed seem to be asking about the privileged role of multiplication in number theory. I think that actually is a more philosophical question, because when you actually study mathematics (as I see from your profile that you have), you find that multiplication is incredibly important and ubiquitous. One of the most important abstract structures in all of mathematics is the ring, which is a set endowed with both additive and multiplicative structure (and at least a few reasonable axioms relating them). The ring of integers has been incredibly interesting and important for at least two thousand years. Are there mathematical structures which abstract the powering operation, for instance? Yes: off the top of my head I can think of restricted Lie algebras and divided power structures. But at most 1% of all mathematicians seriously care about either of those, whereas everyone needs rings. One way to say it is that whenever you have an additive structure, then the collection of maps from that structure to itself which preserve addition is a ring, the endomorphism ring of the structure. (Look up additive categories to see this in detail.)

I would go so far as to say that studying this kind of generalization of multiplication too seriously is a bit of a trap. Moving from addition to multiplication and exponentiation and beyond as operations is a nice intellectual exploration that probably every mathematician makes at some point early on. Armed with the thrill of discovery, it is natural to wonder whether these higher operations -- tetration and beyond -- might actually be more interesting, especially since you don't hear much about them in school. Well, they could have been -- I don't know of a convincing "philosophical" argument that explains otherwise -- but they're not. It becomes a bit of a black hole, and in fact most people who are highly engrossed with tetration turn out to be, if not a bit crankish, then certainly aiming away from where the real mathematical content lies.

In particular, you ask about the properties of integers $n$ which cannot be decomposed as $a^a$, $a^{a^a}$, and so forth. Well, I am a practicing number theorist and I'll give you a piece of practical advice: study the actual primes instead. They are much more interesting than your "primes under the powering operation". I can't prove it to you, but I feel very confident about it. In fact, to the idea that no one has thought of this before: I would say that a lot of people have probably thought about it for a little while and unfortunately some people have probably thought about it for longer than they should, when they could have better used their time thinking about something else.

Further Added: It might helpful to say a little more about why "powering-primes" are so inauspicious. The fascinating thing about the primes is that from a purely multiplicative perspective they are determined by Euclid's theorem that there are infinitely many of them, but when you interact them with the additive structure you get an amazingly rich and fruitful question: where are the prime numbers with respect to the natural (additive) ordering of the natural numbers? The two (incredibly old and famous) questions I asked above are special cases of that. In general, there is an entire branch of mathematics which is concerned with how the primes are distributed: this part of mathematics is deep, contentful and useful (i.e., has many, many applications to other parts of mathematics).

I am not clear on what the precise definition of powering-prime being proposed is, but certainly numbers which are not powering primes should lie among the perfect powers, i.e., numbers $a^b$ for $a,b > 1$. Now the set of perfect powers is certainly well-studied in number theory. (For instance, it is a 2006 result of Bugeaud, Mignotte and Siksek that the Fibonacci numbers are perfect powers are precisely $8$ and $144$. This got published in the leading mathematical journal: it's serious!) Note that the perfect powers, although obviously infinite, form a very small set -- density zero -- in the natural numbers. So in contrast to the primes, which are infinite in number but rare, most natural numbers are (by any definition) powering-primes. Asking about gaps between perfect powers is also natural: the Catalan Conjecture, now Mihailescu's Theorem, is an important result there. So if powering-primes means "not perfect powers" then, sure, this is already a thing...but a thing which is subsidiary to the thing about prime numbers. (See Steve Jessop's answer.)

I should say though that from the OP's example I got the impression that by a powering prime he meant something that is not of the form $a^a$ (or maybe not of this form or $a^{a^a}$ or...: that comes to much the same). That is much less interesting: it's just the image of the positive integers under a rather simple increasing function, so it's quite clear "where these numbers are".

Answer 2

That statement, about primes being the building blocks of the integers, is not a philosophical statement nor an expression of human preference. It is, instead, a human abbreviation of a precise mathematical theorem, known as the "unique factorization theorem":

• Every natural number $\ge 2$ can be expressed as a product of a sequence of prime natural numbers, and that product expression is unique as long as it is written in nondecreasing order.

So for example $16 = 2 \cdot 2 \cdot 2 \cdot 2$, $24 = 2 \cdot 2 \cdot 2 \cdot 3$, $300 = 2 \cdot 2 \cdot 3 \cdot 5 \cdot 5$.

You can see that this statement incorporates "power-primes" by allowing a prime number to be repeated in the product expression. So as far as this statement is concerned there is no special distinction needed for prime powers.

That does not mean that there is nothing special at all about prime powers. They do come up in many other investigations of number theory.

Answer 3

Pete's answer includes this, but I think it is worth stating as an answer alone because I believe it is the crux:

Primes are the multiplicative building blocks of the integers

This is an allusion to the unique factorization theorem.

To improve the precision of Tao's statement, we could say that primes are "one possible set of building blocks of the integers". They are not the only way to generate the integers: one can of course instead do that, as you said, using 1 and addition (together with either -1 or subtraction to include negative integers).

Basically, if you build the integers as a Peano system then the building block is the successor operation (adding 1). If you build them with multiplication then you have a set of blocks, the primes. We're quibbling about the word "the" vs the word "a", which is all about context.

The interesting thing about building them with multiplication is that the set of building blocks has many non-trivial properties. The distribution of primes within the integers is interesting and difficult. The distribution of "the set containing 1 and nothing else" within in the integers is trivial: it's the one at the beginning, after 0, and nothing else! So it's not that mathematicians prefer multiplication, it's that they work on problems they find interesting. And they very quickly solve the ones that aren't difficult, so "interesting and difficult" are necessary conditions for things they study.

As for "why not power-primes?", I suspect (but I'm not sure) that in most applications the useful properties of your power-decompositions can be conveniently expressed in terms of multiplication-decompositions anyway. For example if I'm interested in $19683 = {(3^3)}^3$ then I could instead observe that it's equal to $3^9$ and work with that. A number is power-composite (that is to say, "it's a power") if and only if the greatest common divisor of all the exponents in its prime factorization, isn't 1. That is, if all the exponents are even (such as $324 = 2^2.3^4$: $2$ and $4$ are even) then it's a square (${(2.3^2)}^2$ in my example). If all exponents are divisible by 3 then it's a cube, and so on. The question of what numbers are powers is interesting, but it's frequently studied by looking at their prime factorizations, so the primes remain important in that context too. It seems likely you'd have to study power-primes as well as primes, not instead of.

Answer 4

But you could say the same thing about powers: An integer can be expressed as a (well, I'm not a mathematician and now I'm at a loss for words) power-chain of integers or not. If not, it's called (I don't know what the name could be) "power-prime". For example, 16 = 2^2^2, so it's power-composite, whereas 2 can't be expressed with powers, so is power-prime.

Sure. But so what?

I know that's going to sound like a very flippant question, but - to my mind - it underpins the real answer. I care about primes because - and here's a theorem - every number can be written as a product of them, and indeed in one unique way. That's an incredibly useful property in a lot of ways: it tells me that, if I want to understand a number, I can break that number up into smaller pieces and then just understand those pieces.

Here's a very simple illustration of how understanding the pieces can be useful: what's the highest common factor of $392040$ and $74844$? What's their product? What do you get when you divide the first by the second? I have no idea, personally, and I don't much want to work it out.

Now, what's the highest common factor of the following two numbers? $$2^3\times 3^4\times 5^1\times 7^0\times 11^2$$ $$2^2\times 3^5\times 5^0\times 7^1\times 11^1$$ Without any thought, you can immediately write down the answer $$2^2\times 3^4\times 5^0\times 7^0\times 11^1$$ by simply taking each prime factor in turn. Multiplying them is just as easy: $$2^5\times 3^9\times 5^1\times 7^1\times 11^3$$ And so is dividing the first by the second: $$2^1\times 3^{-1}\times 5^1\times 7^{-1}\times 11^1$$ $$(= \tfrac{2\times 5\times 11}{3\times 7})$$ And of course, as you've probably guessed, the first pair of numbers I gave you and the second pair were in fact the same pair of numbers, but the second time round I gave them to you in nice simple pieces rather than in ugly, difficult-to-understand lumps.

That's not to say breaking things up into prime factors makes things simpler all the time. Actually, while multiplication is great, addition is a nightmare: what's $(2^3\times 3^4\times 5^1\times 7^0\times 11^2) + 5$? (Turns out it's $5\times 89\times 881$, but I had to cheat and run it through my computer to work that out.)

There are much more sophisticated examples of where we use this prime factorisation theorem in number theory and cryptography. But ultimately, it comes down to the following: we care about prime numbers because they're useful. They're sort of the multiplicative equivalent of a tally (you made this point yourself, and I agree). The claim that they are "the building blocks of the integers" is slight sensationalism, but you can see above how fundamental they are in things like the multiplicative structure of the integers.

Maybe power-primality is useful too. Can you show me why? :)

Answer 5

1. One thing I agree with -- it is absolutely true that the integers are generated as an additive group by 1, and that this is important. When we say that the primes are the "building blocks" we mean that they tell us something about the multiplicative structure of the integers.

2. If we understood all the primes perfectly (say if we had an oracle that told us what the $k$th prime number is) then we would understand all the power-primes perfectly. They are precisely the numbers whose prime factorizations aren't powers of a prime. So in fact I disagree with your argument that there are infinitely many interesting operations we can put on the integers (that are compatible with the additive structure) and they each generate mysterious sets of "primes."

3. I suppose you could say "the primes are the building blocks of the multiplicative structure on the integers and the building block of the additive structure is the number 1" and this would be more accurate than the statement you are quoting! I don't think the statement as it is usually quoted is misleading though, just brief -- it's a metaphor anyway.

Answer 6

The unique factorisation of natural numbers is also known as the "Fundamental Theorem of Arithmetic", because experience has shown that the property it expresses is fundamental to our understanding of arithmetic. So much is "elementary".

But there is a deeper understanding of the primes as the building blocks, which takes into account the existence of prime powers. In more advanced work use is made of the $p-$adic numbers, in which the properties of a system with respect to each particular prime can be investigated (we sometimes say "locally at $p$"). This is a powerful technique, particularly if we have a way of stitching the pieces belonging to each prime together. And in this context the primes really are the building blocks.

One reason this works so well is that the integers modulo a prime form a field - there are no divisors of zero. If we tried $6$ instead we'd have $3\times 2 = 6 \equiv 0$, and $9$ would give $3\times 3 = 9 \equiv 0$. With the primes, the "pieces" have no overlap, as it were.

So the comment about primes being building blocks is both a useful way of thinking about the primes in an elementary way, and an expression of some deeper mathematical insights about the integers.

Answer 7

As Pete L. Clark mentions in his excellent answer the statement "the primes are considered to be the 'building blocks' of the integers" is a soundbite - a shorthand way to refer to a very important fact about the natural numbers and by extension, of the integers.

The additive structure of the integers is relatively trivial, but once we bring multiplication into play things start to get interesting! The multiplicative structure of the integers is most definitely not trivial, and the primes can certainly be considered to be the building blocks of that structure. So it's no wonder that primes and their properties have been a topic of study since the dawn of mathematics.

As its name suggests, the Fundamental Theorem of Arithmetic is a core theorem of number theory. OTOH, even if the integers didn't have unique factorization the primes would still be important. But I guess such speculation is a matter for philosophers, not mathematicians.

There is no simple function that generates the primes (and only primes), there isn't even a simple formula for counting the number of primes less than a given n. If there were, I suspect that the multiplicative structure of the integers would be a lot simpler. :)

Curiously, there are systems of Diophantine equations that generate primes, e.g. the system created by Jones et al., but they are of no use in actually finding primes, since they amount to algebraic encodings of prime sieve algorithms. See Wikipedia for details.

Steve Jessop mentioned the Riemann zeta function in his comment on Pete L. Clark's answer. The connection between the Riemann zeta and prime numbers arises from the beautiful Euler product formula:

$$ \sum_{n=1}^\infty\frac{1}{n^s} = \prod_{p \text{ prime}} \frac{1}{1-p^{-s}}, $$

The proof of this remarkable identity does not require advanced mathematics. To my mind, the Euler product formula nicely show-cases primes in their role of fundamental building blocks.

Answer 8

You are correct that there are multiple ways of looking at numbers, and describing primes as the unique building blocks of integers may not be strictly correct.

I teach my students that primes are "number atoms". If you break natural numbers down multiplicatively, then eventually you get indivisible numbers - the primes, or number atoms. If you are wanting to make a composite number, the equivalent of a molecule, you need to make sure you put together the right number of atoms of the right kinds.

You can make water out of $H_2$ and $O$ (half of $O_2$), or alternatively $H$ and $HO$ (as in a water solution). Similarly, $20$ is $4 \times 5$ or $2 \times 10$, but in reality it is simply $2^2 \times 5$ either way.

If we agree that atoms are the building blocks of molecules, it follows by analogy that primes are building blocks of natural numbers.

HOWEVER

It is equally true that numbers can be broken down according to addition, and so we also give $1$ a special name in natural numbers. This is the basis of an axiomatisation of arithmetic and many theorems.

Similarly, I think it may also be possible to analyse rational numbers either as pairs of relatively prime integers or as Gaussian Primes, or as continued fractions, or... The useful perspective depends on the application.

The complex relationship between addition and multiplication, is still being actively researched. However, by itself, the theory of $1$ is not as rich as the theory of prime numbers, so a mathematician is much more likely to think of primes as interesting building blocks.

Answer 9

Kaplan and Kaplan's The Art of the Infinite (fantastic read, by the way) touches on this. Indeed, it goes into some depth about the sheer leap from 1 as the sole additive "building block", to all the primes being the multiplicative "building blocks". (I don't recall if the term "building block" was used, but the notion is there.)

I can't speak for Terry Tao or other mathematicians, but I would mean there to be an implicit "multiplicative" (as in the previous paragraph) if and when I called the primes the building blocks of the integers. In that sense it is wholly correct.

Your question seems to acknowledge this and go on to ask why it's multiplication that's implied. You're probably right about multiplication being "complicated enough to be interesting to us", though not, I think, about powers being "bewildering". "Building" integers through addition is trivial, and so multiplication is merely the first non-trivial operation we come to. (First, in the sense of multiplication being "meta-addition", powers being "meta-multiplication", etc.)

Answer 10

http://en.wikipedia.org/wiki/Fundamental_theorem_of_arithmetic

So while $1$ generates all the integers under addition, the primes generate all the integers under multiplication. I think Tao mentioned this on the Colbert Report or maybe I am just imagining things.