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

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).

Solution 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".

Solution 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.

Solution 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.