The fundamental theorem of arithmetic states that every positive integer can be factorized in one way as a product of prime numbers. This statement has to be appropriately interpreted: we count the factorizations and as the same, for instance. Note that it is essential not to count 1 as a prime, or else we could stick a product of 1s on to the end of any factorization to get a different one: . But doesn’t that mean that 1 itself cannot be written as a product of primes? No — we define the “empty product” (what you get when you take a bunch of … no numbers at all and multiply them together) to be 1. That is a sensible convention because we would like multiplying a product of numbers by the empty product not to make any change to the result.
That’s enough about what the fundamental theorem of arithmetic says. In this post I want to discuss the question of why it is a theorem at all. Isn’t it more like an observation? After all, given any number, we can simply work out its prime factorization.
Answer 1. If you think it’s obvious, then you’re probably assuming what you need to prove.
If you say, “we can simply work out its prime factorization,” you are already assuming that that factorization is unique. Otherwise, you would have had to say, “we can simply work out a prime factorization for it”. Of course, if you say it that way, it suddenly doesn’t seem quite as obvious that there’s only one. If you’re trying to argue that it’s obvious and you ever utter the phrase, “the prime factorization,” then you are begging the question, since implicit in those words is the assertion that there is only one prime factorization.
Answer 2. Just because you’ve got a completely deterministic method for working out a prime factorization, that doesn’t mean what you work out is the only prime factorization.
The following method is probably how you factorize a number: you divide it by 2 as many times as you can (which may be no times at all), then by 3, then by 5, and so on, keeping track of what you’ve done. For example, if your starting number is 575, then you can’t divide it by 2 or 3, but you can divide it by 5 to get 115, and then by 5 again to get 23, and then … well, you’ll probably know that 23 is prime, but you could also argue that since is greater than 23 and you’ve checked 2 and 3, then it must be prime.
But just because that method always gives the same answer (the method in the abstract being to keep dividing by the smallest prime that goes into the number you see in front of you), that doesn’t mean that there might not be some other method that gives a different answer. For example, what if you looked for the largest prime that went into your number? You’re probably thinking that you’ll just get the same list of primes, but written backwards. But how do you know this? Obviously that’s what you’ll get if there’s only one way of writing the number as a product of primes, but that’s what we’re trying to prove. If there’s another way of writing it as a product of primes, then perhaps the largest prime in the other way of doing things is larger than the largest prime that results from the usual method.
Answer 3. Look, it just bloody well isn’t obvious, OK?
Sorry, I lost it for a moment there. But if you persist in thinking that it’s obvious, then perhaps you can tell me why it is obvious that is not the same number as . I’ll save you a little time by revealing that all of 23, 53, 769 and 1759 are prime. I will not accept as an answer that if you calculate those two products you get different results. That to me is an admission that it wasn’t obvious that the answers would be different. If it was obvious, then why bother to calculate them?
By the way, I’ll grant you that sometimes it’s obvious that two products of primes are different. For example, if 2 is involved in one product and not the other, then the first product is even and the second is odd. However, even that second assertion depends on the (simple) result that a product of odd numbers is odd. We’d be able to see instantly that if we knew that a product of two non-multiples of 23 was always a non-multiple of 23. But is there an easy way of showing that? We can work out the multiplication table mod 23, but that’s a bit tedious. Alternatively, we can use some theory from the course — but unless you’re finding the course so easy that that theory (a proof derived from Euclid’s algorithm) is utterly obvious, then I don’t think you can call it obvious that .
Here’s another pair of products of primes for your delectation and delight: and . Are they obviously different? It’s not clear which is bigger — they’re both a little over 40,000. What about the last digit? Damn, 1 in both cases. OK, let’s go for the second last digit, which is a bit of a cheat but still. In the first case we get the last digit of , which is 6. In the second case we get the last digit of , which is again 6. So we’ve got two numbers that are a little bit above 40,000 that both end 61. As it happens and .
If you wanted a quicker demonstration that those two numbers are different, you could work out what they are mod 3, which is a lot easier than working them out completely. But that’s not going to work in general. For instance, it doesn’t work for the first example, where the smallest modulus for which they differ is 7. If I took two pairs of absolutely huge numbers (with millions of digits), I could get them to agree in almost all their digits and differ by a multiple of, say, 1000! And even if such small-modulus tests can be used, it isn’t obvious in advance that they will work if it isn’t obvious in advance that the products are different.
Answer 4. If it’s so obvious that every number has a unique factorization, then why is the corresponding statement false in a similar context?
Consider the collection of all numbers of the form where and are integers. (You might prefer to write these numbers as , but I prefer for reasons that I don’t want to go into here, but might mention in a future post.)
These numbers have various properties in common with the integers: you can add them and multiply them, there are identities for both addition and multiplication, and every number has an additive inverse. And as with integers, if you divide one by another, you don’t always get a third, so the notion of divisibility makes sense too. That means that we could if we wanted try to define a notion of a “prime” number of the form .
Just before I try to do that, let’s quickly decide what we mean by a prime when we allow negative numbers. Presumably we’re going to want, say, to be a prime, but what definition will lead to that? The small technical obstacle we face is that if we allow negative primes like that, then for a somewhat silly reason factorizations won’t be unique: for instance, . The usual approach to this is to divide numbers into three kinds: prime numbers, composite numbers, and units. A unit is a number that has a multiplicative inverse, so in the units are 1 and -1. A prime is a number that cannot be written in the form unless exactly one of and is a unit. (I said “exactly” one because I didn’t want accidentally to define units themselves to be primes.) And now we can express the fundamental theorem of arithmetic in by saying that every number has exactly one factorization into primes, except that we count two factorizations as the same if the only difference (apart from the order) is that the primes in one factorization are multiplied by units to give the primes in the other factorization. For example, we count and as the same, since we can reorder the second factorization as and then multiply both primes by the unit -1 to get , which gives us the first factorization.
In short, what we’re saying is that if two products of primes don’t obviously give the same number, then they give different numbers.
Right, back to numbers of the form . Let’s check that 2 is a prime in this ring. (A ring in this context is, roughly speaking, an algebraic structure with addition and multiplication with all the usual axioms apart from the existence of multiplicative inverses. You can think of it as something a bit like . However, the actual definition is a bit more general, as you can find out from the relevant Wikipedia article. Hmm, I’ve just looked at that article and I don’t like it at all: the list of examples is woefully inadequate. The important examples are eventually mentioned, but not in the list of basic examples, so you don’t get a good idea that they are the important ones.) First of all, 2 isn’t a unit, since is not of the form . The modulus of is , so if , then the modulus of is bigger than 2. It follows that the only way of writing 2 as a product of non-units would have to be to write it as a product of non-unit integers, which we can’t. So 2 is prime.
A similar check can be run for 3. So 2 and 3 are primes. It’s also possible to show that and are primes. But , so 6 has a non-unique factorization into primes. (It’s also easy to see that you can’t multiply or by a unit to get one of .)
Why is this a problem for people who hold that the fundamental theorem of arithmetic is obvious? It’s because they have to explain what it is about that is relevantly different from the ring of numbers of the form , which is denoted . Why can’t we just translate any proof that works for into a proof that works for ?
Here’s an example of how you can use to defeat somebody who claims that the result is obvious in . Let’s take the argument that you can just work the factorization out by repeatedly dividing by the smallest prime that goes into your number. Well, you can do that in as well. Take 6, for instance. The smallest prime (in the sense of having smallest modulus) that goes into 6 is 2. Dividing by 2 we get 3, which is prime. So we’re done. So there can’t be another factorization. Except that there is another factorization. So the argument just isn’t an argument.
In a future post I’ll discuss the proof of the fundamental theorem of arithmetic. But this post is just to try to convince you (if you needed convincing, which you may not have) that the result is worth going to some effort to prove.