Walls have bricks, elements have atoms, organisms have cells, and a bowl of Lucky Charms has little fake marshmallows. Walls, elements, organisms, and Lucky Charms all break down into smallest indivisible units. Although a single brick or Lucky Charm is not particularly fortifying or filling, they are the irreducible pieces.
Most natural numbers (the numbers 1, 2, 3, 4, 5, etc.) can all be thought of as sums of smaller natural numbers. For instance, 3 is 2 + 1 so, at least in terms of adding, we say that 3 is reducible, because we can reduce it to a sum of smaller natural numbers. However, 2 is also reducible because (as you may remember from younger days) it is a sum of smaller numbers, namely 1 and 1. 1, however, can’t be written as a sum of smaller natural numbers, so it’s irreducible. In fact, in terms of adding, 1 is the only irreducible natural number.
It’s a lot more interesting to split up numbers as products of smaller natural numbers. For instance, we can think of 30 as 6 x 5. In terms of multiplication, 6 is reducible because 6 is 2 x 3. 5, however, is not. If we try to split it up as the product of smaller natural numbers, we notice all we can do is write it as 5 x 1 and of course 5 isn’t any smaller than itself. For the same reason, 2 and 3 are also irreducible.
We’ve stumbled on an important difference between addition and multiplication: there is only one natural number (the number 1) that is irreducible with respect to addition, but there are multiple (2, 3, 5, and more) that are irreducible with respect to multiplication. Compare this to our physical “irreducible parts” analogies. All you need is a bunch of gold atoms to make a nice, sturdy golden calf. And all you need is a bunch of identical bricks to keep the Mongols at bay. But for a human to do the Robot he needs a wide variety of cells for breathing, arm movement, and the rigid, mechanical-looking neck control that makes it the greatest dance of all. Similarly, a bowl of Lucky Charms is hardly a bowl of Lucky Charms at all unless it has hearts, stars, and clovers.
Except for 1, which is kind of its own thing, we call the irreducible (with respect to multiplication) natural numbers prime. If you think back to a math class from long ago or do a quick Google search, you might remember that the first few primes are 2, 3, 5, 7, 11, 13, 17, 19, 23, … Even though they have a pretty simple definition, the prime numbers have all kinds of interesting properties. For instance you’ll notice that after 2, all the primes are odd. If you think about what it means to be even, you might be able to figure out why. A subtler property is that if you write the prime numbers in order, you’ll notice that there are never 3 consecutive odd numbers after 7. For instance, the list above has 11 then 13 but skips 15 because 15 = 3 x 5 so it’s not prime (for future reference we use the word composite for natural numbers that aren’t 1 and aren’t prime). After that the list has 17 then 19 but skips 21 because 21 = 3 x 7. This is a little more difficult; if you’re up for a challenge grab a pencil and give it a shot.
But there’s a more interesting and fundamental question that we’re going to answer. If there are many, many different types of cells in the human body and at least that many different marshmallow shapes in a bowl of Lucky Charms (citation needed), how many different primes are there? The answer is that there are infinitely many and the original proof (a brainchild of Euclid, father of geometry and scourge of the high school junior) is ancient, brilliant, and, in my opinion, beautiful. Let’s start with some intuition.
Suppose that you look at my list of primes above and decide to keep scanning to see if the primes go any higher. You try the next odd number, 25, and notice that it’s 5 x 5 so it’s composite. Then you try 27 and notice that it’s 3 x 3 x 3 so it’s also composite. At that point, if you’re a really lazy detective, you might say, “I think we got them all. Break out the champagne!”
I want to show you that you’re wrong. This approach might seem weird, but it will make the problem as a whole much more intuitive. I say, “before you pop the cork (remember to aim away from your face) let’s consider the number (2 x 3 x 5 x 7 x 11 x 13 x 17 x 19 x 23). It happens to come out to 223,092,870 but that’s not particularly important. If we were to split 223,092,870 objects into piles of 2, we would get a natural number of pairs, namely (3 x 5 x 7 x 11 x 13 x 17 x 19 x 23). If we were to split 223,092,870 objects into piles of 23, we would get a (different) natural number of piles of 23, namely (2 x 3 x 5 x 7 x 11 x 13 x 17 x 19). The upshot is, if we tried to split 223,092,870 objects into piles of 2, 3, 5, 7, 11, 13, 17, 19, or 23, whichever one we chose we would get a natural number of piles of that many.
What if we add 1 to that number to get 223,092,871? If we tried to split it into piles of 2, we would again get (3 x 5 x 7 x 11 x 13 x 17 x 19 x 23) pairs but this time we would have one left over. That means that 2 is not a factor of 223,092,871. Similarly, if we tried to split 223,092,871 objects into piles of 2, 3, 5, 7, 11, 13, 17, 19, or 23, whichever one we chose we would get a natural number of piles of that many and an extra one left over. That means our number 223,092,871 can’t be divisible by any of the prime numbers on that list. Either 223,092,871 is a prime number, in which case you were wrong to assume that list of primes was complete, or it’s a composite number so it splits into prime factors. But, since none of its prime factors is on that list, the list can’t possibly be complete.
The reason I showed you this round-about proof instead of pointing out that 29 is prime and lecturing you on the importance of perseverance is that the last paragraph is almost the proof that there are infinitely many primes. What if instead of that list, you guessed there were 26 primes and call them A, B, C, … , Y, and Z? I would direct your attention to the number (A x B x C x … x Y x Z). Since A, B, C, … , Y, and Z are all factors of it, just like before we know that none of them can be a factor of (A x B x C x … x Y x Z) + 1. That means that either (A x B x C x … x Y x Z) + 1 is prime or it is composite and it splits into prime factors, none of which can be A, B, C, … , Y, and Z. Either way there must be more than 26 primes.
And what if you guessed there were 332 primes? Then I would multiply together all 332 of them and add 1 and you would see that there must be at least 333. You can guess that there are any number of primes, a million, a billion, or a greenblattillion and I can multiply them all together and add 1, proving to you that there are at least a million and one, a billion and one, or a greenblattillion and one.
The only way this could possibly work for any number you guess is if there are infinitely many primes, so that must be the case. And that’s the proof. Even to this day, the brightest minds in the world are trying to better understand how concentrated the primes are as they go further and further down the number line, leading to questions that only make sense because there are infinitely many. For instance, at least as of my writing this article (by the time you read it, who knows?), it’s still not known if there are infinitely many pairs of prime numbers that are 2 apart from one another.
I love the proof for 3 reasons: (1) The fact that there are infinitely many prime numbers is remarkably deep and set into motion literally millennia of exciting research. (2) The ideas are pretty simple; the whole thing basically comes down to the definition of a prime number and some creativity. (3) The proof is a game where I get to win infinitely many times.
