This post is part of the What is Maths series.
Up until this point, it has looked like addition and multiplication are really very similar. Both addition and multiplication are commutative. Both addition and multiplication are associative. There is also a cancellation lemma for multiplication, although with a small difference; it states that if \( a \times b = a \times c \) and \( a \neq 0 \), then \( b = c \).
Furthermore, some of the basic facts (which I won’t prove here) regarding ordering and divisibility are also disturbingly similar. We also have that if \( a \mid b \) and \( b \mid a \), then \( a = b \). In addition, if \( a \mid b \) and \( b \mid c \), then \( a \mid c \).
However, we shall now start to explore the differences between addition and multiplication. It turns out that they are in fact wildly different. One of them can be thought of as tame, while the other is a wholly chaotic beast. As a first peek, we know that for any natural numbers \( a \) and \( b \), we have either \( a \geq b \) or \( b \geq a \) but the corresponding statement about multiplication is not true. For example, neither \( 2 \mid 3 \) nor \( 3 \mid 2 \) is true.
Let us now imagine that we want a way to describe the numbers without referring back to the successor operation. We would like our method to use as few ‘symbols’ as possible; for this discussion, numbers like 10 will be considered a single unique symbol, and not composed of the symbols 1 and 0.
Our first option is simply to replace the successor operation with ‘+’ and ‘1’. As we noted earlier, addition by 1 is exactly the same as taking the successor, so, in combination with 0, these three symbols are all we need. You may be concerned that large numbers are somewhat impractical to describe using this method, but the crucial fact is that it is possible to describe them—the amount of patience needed to do so is irrelevant!
Now, for contrast, what if we wanted a multiplication based scheme instead of an addition based scheme. Because we know that \( a \times b \geq a \) whenever \( b > 0 \), our scheme must still include 0 and 1; they cannot be constructed by multiplying together larger numbers. However, with just ‘\( \times \)’, ‘0’, and ‘1’, we actually cannot construct any numbers larger than 1. Therefore, we must add ‘2’ to this scheme. With this addition, we construct quite a few additional numbers: 4, 8, 16, 32, and so on. But we are still missing some: 3, for example. So again, we add ‘3’ to the scheme. Despite this, we still cannot make the number 5, so this must also be added. On and on we can go, but it will turn out that no finite multiplication based scheme of this form is sufficient (we will prove this later).
In general, this idea of looking for the ‘building blocks’ of some collection, which can be combined with some operation to produce the whole collection, is really quite useful. In some sense, it reduces the problem of understanding the collection into just understanding these building blocks and the way they combine. In this particular case, the radical differences between the building blocks with respect to addition and with respect to multiplication are deeply revealing.
Prime Numbers
The building blocks of the natural numbers with respect to multiplication are (except for 0 and 1) the prime numbers, a concept I’m sure you’re already familiar with. In fact, we have already developed enough knowledge on top of the axioms that we can use the traditional definition.
Because any number is divisible by itself and 1, this is equivalent to the alternative version of the definition: that a prime number is a number divisible only by itself and 1. However, the definition given above makes it a little clearer that we do not wish to consider 1 a prime (this is usually done as it is necessary for prime factorisations to be unique, although we won’t prove that here).
We should now choose some familiar numbers and ask whether or not they are prime. To do so, we will benefit from using a result that follows from a few of the facts given at the end of the previous part: if \( a \mid b \) and \( b \neq 0 \), then \( b \geq a \).
Firstly, 6 is not prime: \( 2 \times 3 = 6 \) so \( 2 \mid 6 \) (this is enough because we already know 1 and 6 divide 6). Now, let’s ask whether 3 is prime. Because of the fact above, we only need to check numbers less than or equal to 3 for divisibility. We already know that 1 and 3 divide 3, so the only other numbers we need to check are 0 and 2. However, 0 divides nothing other than itself, leaving one number left to check. We now consider the sequence \( 2 \times 0 = 0 \); \( 2 \times 1 = 2 \); \( 2 \times 2 = 4 \); \( 2 \times 3 = 6 \); and so on. We can argue that 3 isn’t in this sequence because the sequence is increasing (can you prove this?) and we have already passed 3 without it appearing in the list. Therefore, 3 is not divisible by 2 and so 3 is prime!
While that was a little onerous, a very similar method can be used to test the primality of any other number you are concerned about.
We must now return to our question of building blocks. Certainly, any prime number must be a building block, for it cannot be made by multiplying together two different numbers. However, it is not at all clear that the primes are enough to be the building blocks by themselves; we shall now try to prove that this is the case. To do so, we will make use of a rather fundamental fact: any non-empty collection of natural numbers has a minimum. I suggest you try to prove this using induction—the link between this fact and induction is so deep that they can actually be thought of as equivalent. What’s more, this link transcends the context of natural numbers, although we won’t go any deeper into it for now.
We now consider the collection of natural numbers that are greater than or equal to 2 and cannot be written as a product of prime numbers. Call this collection \( C \).
Because we are supposing the hypothesis to be false, this collection must not be empty and therefore has a minimum.
Let us call this minimum \( n \).
Now, if \( n \) were prime, then we could use a sequence of length 1, with the only number in the sequence being \( n \).
However, as \( n \) is in \( C \), it cannot be written as a product of primes.
Therefore, this means \( n \) must not be prime.
Conversely, if \( n \) were not prime, then we could write \( a \times b = n \) for some suitable choice of natural numbers \( a \) and \( b \). We can further choose \( a \) and \( b \) such that they are both greater than 1, or equivalently, greater than or equal to 2.
Furthermore, we know that \( n > a \) and \( n > b \).
As \( n \) is the minimum in \( C \), this means that neither \( a \) nor \( b \) are in \( C \).
Therefore, we can choose primes \( p_1, p_2, \ldots, p_r \) such that \( a = p_1 \times p_2 \times \cdots \times p_r \).
We can also choose primes \( q_1, q_2, \ldots, q_s \) such that \( b = q_1 \times q_2 \times \cdots \times q_s \).
This means that \( n = p_1 \times \cdots \times p_r \times q_1 \times \cdots \times q_s \).
However, as \( n \) is in \( C \), it cannot be written as a product of primes.
Therefore, this means that \( n \) cannot be non-prime, or, in other words, \( n \) must be prime.
However, it cannot be the case that \( n \) is prime and is not prime at the same time!
Therefore, our assumption that the hypothesis was wrong must have been incorrect.
This proof makes use of a technique called ‘proof by contradiction’, a strategy we haven’t seen before that can often seem rather bizarre. Its more historic name is ‘reduction to the absurd’, which makes the strangeness of it clear in the title.
The reason it comes across as rather suspect is that the very first line of the proof states that we are going to assume the statement which we are trying to prove is actually wrong. We then work for a while in a nonsensical wonderland-style system of maths in which numbers can be both prime and not prime. Finally, we proclaim that the system we were working in throughout the proof is nonsense and so our statement is actually true.
To see why this works, we must consider what the consequences of just assuming a statement to be true (or false) are. If we are correct in our assumption, then everything is fine and we continue working in the regular number theory. If, however, our assumption is incorrect, then we have entered wonderland. The goal of a proof by contradiction is to show that, when assuming some statement is false, we enter wonderland. A classic way of doing this is to show that some other statement is both true and false, in our example above this is the claim that \( n \) is prime. The other way this is often done is by ‘disproving’ some result that we know to be true; ‘disproving’ the claim that \( 1 \neq 0 \) is a favourite!
You may also have noticed that my proofs have become a little less rigorous—this is intentional. At this stage of our development of number theory, the proofs become more focused on concepts and less on ‘symbol shunting’. While it is certainly possible to retain the level of rigour from the original proofs, I believe it would only obscure the proof’s spirit.
The Quantity of the Primes
We know a few prime numbers, but we may now wonder just how many there are? How many building blocks do we need to describe any number using multiplication? To answer this, I shall defer to Euclid, who solved this problem over 2000 years ago with what I consider to be one of the most elegant arguments in number theory.
Then we can list all the primes \( p_1, \ldots, p_n \), and this is certainly a non-empty list (2 is prime).
We can now consider the successor of their product: \( P = 1 + ( p_1 \times \cdots \times p_n ) \).
By the claim above, \( P \) can be written as a product of primes. In particular, there is some prime \( p \) such that \( p \) divides \( P \).
Now, as \( p \) is prime, it is in the list \( p_1, \ldots, p_n \) so \( p \) certainly divides \( p_1 \times \cdots \times p_n \).
Therefore, \( p \) must also divide the difference between \( P \) and \( p_1 \times \cdots \times p_n \), which is 1.
But no prime divides 1, so this is a contradiction.
There must, therefore, be infinitely many primes.
Despite knowing that there are infinitely many primes, we may feel that we haven’t fully answered the question of how many there are. In some imprecise sense, we may feel like there are more multiples of 4 than there are multiples of 2, even though there are infinitely many of both. There are many directions we could approach this question from but for now we shall approach this by asking how big the gaps between two consecutive primes are, where consecutive primes are those that have no other primes between them. In another twist, we shall answer this question by instead thinking about how long a sequence of consecutive non-primes we can find.
Let \( X = 1 \times 2 \times \cdots \times n \times ( n + 1 ) \).
Let \( n \) be a natural number such that \( n > 2 \) and \( N + 1 \geq n \).
Then \( n \) is contained in the product that produces \( X \), so \( n \mid X \).
We also trivially have \( n \mid n \), so \( n \mid X + n \).
Also, as \( N \neq 0 \), we have that \( X + n \neq n \).
Therefore, as \( n \neq 1 \) also, we must have that \( X + n \) is non-prime.
Finally, the sequence \( X + 1, X + 2, \ldots, X + (N + 1) \) contains \( N \) consecutive non-prime numbers.
It now follows from this result that you can find consecutive primes with as large a gap between them as you want. We can take this result to suggest that the prime numbers are extremely rare, something seemingly at odds with there being infinitely many of them!
Conclusion
It is quite amazing to now go back to the axioms and see just how far we have come from. We started talking about nothing more than 0 and \( S \) and are now discussing a wealth of concepts: addition, multiplication, ordering, prime numbers, and more. It is also startling to look back at those early proofs. We started with proofs that involved a lot of pushing symbols around and these final proofs forego the heavy use of symbols and instead connect concepts and ideas.
While I doubt that many of the facts we’ve proven here are new to you, I hope that you will have gained an appreciation for the connections between them and the logic underpinning them. On top of that, though, you are now equipped with the mathematical tools needed to develop your own proofs and further explore number theory. In fact, I encourage you to do just that and will finish this series by presenting a few problems for you to experiment with!
A Selection of Number Theory Problems
- Let us call a number \( n \) ‘square’ if there is a number \( r \) such that \( r^2 = n \). Which numbers can be written as the sum of two squares?
- A prime triple is a set of three numbers that can be written as \( p \), \( p + 2 \), and \( p + 4 \) and are all prime. How many prime triples are there?
- Can you prove that if \( a \mid b \) and \( a \mid c \), then \( a \) divides the difference between \( b \) and \( c \)? You may notice that we relied on this fact in the proof that there are infinitely many primes.
- Show that, if \( p \) is a prime larger than 3, then \( p^2 \) is 1 larger than a multiple of 24.