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

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.

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