I’ve mentioned the fundamental theorem of arithmetic a few times on this blog, so it’s probably time for it to be a theorem of the week. I’ll state it straightaway.
Theorem (the fundamental theorem of arithmetic Every integer greater than 1 can be expressed as a product of primes, uniquely up to reordering the factors.
For example, , and while I can also write it as , this is just reordering the factors — it’s not a genuinely different factorisation. Prime numbers also have prime factorisations: the prime factorisation of 17 is simply 17.
Note that the fundamental theorem of arithmetic is one good reason why it’s convenient to define 1 not to be a prime. If it were prime, we could add as many factors of 1 as we liked to the prime factorisation of a number to get lots of different (but not interestingly different) factorisations.
This is a really important theorem — that’s why it’s called “fundamental”! It tells us two things: existence (there is a prime factorisation), and uniqueness (the prime factorisation is unique). Both parts are useful in all sorts of places. The existence part is useful because it tells us that the primes are somehow the “building blocks” of the integers, and this helps with lots of things. The uniqueness part is useful because it allows us to do certain things that would otherwise not be possible. For example, if we know the prime factorisation of , then we know the prime factorisation of , safe in the knowledge that can’t also have some other prime factorisation.
A useful lemma
Before I tell you about a proof of this theorem, there’s a preliminary result that we’ll need. It’s jolly useful in all sorts of places.
Lemma Let be a prime, and suppose that divides the product . Then divides or divides .
(As usual in mathematics, the “or” here is inclusive, in the sense that we could have dividing both and .)
This really is a property of primes. For example, 6 divides , but 6 divides neither 3 nor 4. (Intuitively, I like to think that this is because we can break up 6 into , and the factors here can divides the factors 3 and 4 separately.) In fact, this property is sometimes taken as the definition of a prime number. In that case, one would then show from this definition that a prime number can be divided only by itself and 1. But since most people are more familiar with the definition of a prime as a number divisible only by itself and 1, I’m going to stick with that definition and show you how to prove the lemma. I’m going to use Bézout’s theorem, so if you don’t know that result you might like to read about it now (and then come back here afterwards!).
Proof of lemma We have a prime , and we know that it divides the product . Let’s suppose that doesn’t divide . Then our goal will be to show that divides .
Now if doesn’t divide , then and are coprime. As usual, we try using Bézout’s theorem to turn this into a positive statement: there are integers and such that .
We know that divides , so we should try to get something containing . Let’s multiply our equation by : we get .
Now divides each term on the left-hand side, so it must divide the right-hand side. That is, divides , as we wanted.
Proof of the theorem
Now we are well placed to tackle the proof of our main theorem, the fundamental theorem of arithmetic. We’ll do the two parts (existence and uniqueness) separately.
Existence We need to show that every integer greater than 1 has a prime factorisation. To do this, we shall use the idea of a minimal counterexample. If the result isn’t true, then there must be a smallest number that doesn’t have a prime factorisation. Let’s call it .
Now can’t be prime, because if were prime then it would have a prime factorisation: itself. So is composite. That is, it is a product of two smaller numbers, say .
Then and are less than , and is the smallest number not having a prime factorisation, so and must have prime factorisations. But then has a prime factorisation: simply multiply those of and .
So there can’t be a counterexample, so the result must be true.
Uniqueness Now our job is to show that every integer greater than 1 has a unique prime factorisation.
So let’s suppose that we have a number with two factorisations: . Here , …, , , …, are primes, not necessarily distinct (we can have or whatever). Our aim is to show that in fact these two factorisations are the same.
If any is equal to some , then we can cancel those factors. Let’s do that wherever possible. We hope that in fact we now have no primes left on either side, because then we’ll know that the two factorisations were the same (they contained exactly the same primes). So let’s suppose that isn’t the case and try to obtain a contradiction.
We have something like , where each is not equal to any .
Now divides the right-hand side, so it must divide the left-hand side too. Using our lemma repeatedly, we see that means that divides for some . But and are both prime, so this says that — and we’ve assumed that not to be the case.
This gives the contradiction we wanted, so the factorisation is indeed unique.
Of course, Wikipedia has a page about the fundamental theorem of arithmetic. The theorem should be described in any decent introduction to number theory. As usual, I shall mention Davenport’s The Higher Arithmetic at this stage.
It turns out that there are settings (number fields) in which one can do number theory, but where one does not necessarily have unique factorisation. This leads to a lot of extremely interesting mathematics — perhaps I shall return to it in a future theorem of the week. There’s so much interesting maths out there!