How much of the standard proof of the fundamental theorem of arithmetic follows from general tricks that can be applied all over the place and how much do you actually have to remember? At first it may seem as though you have to remember quite a bit: there is a non-obvious sequence of lemmas, starting with Bézout’s theorem, continuing with the clever proof that if then either or , bumping that up to a proof for bigger products, and eventually deducing the theorem itself.
But what if one were simply asked to come up with a proof? Would there be any chance of discovering that sequence of lemmas? I maintain that there would — if, that is, you are aware of certain general tricks.
Let’s imagine, then, that we don’t know the proof and are trying to work it out. I’ll split the whole process up into a number of steps. I’ll precede the description of each step by a slogan that more or less generates the argument.
1. State the problem carefully and give names to things.
Loosely speaking, the theorem states that every positive integer can be factorized in exactly one way. Almost always, if you want to prove that something happens exactly once, then you need to show that it happens at least once and that it happens at most once. So in this case, when we state the problem carefully we end up splitting it into two claims, as follows.
Claim 1. Let be a positive integer. Then there exists a sequence of prime numbers such that .
Claim 2. Let and be two sequences of primes and suppose that . Then and there is a permutation of such that for every .
There was some choice about how I gave the formal statements of those two claims — if you think that you wouldn’t have stated Claim 2 in the way that I did, then that’s absolutely fine. Just to emphasize this point, here’s another way of stating Claim 2. (And there are many more.)
Claim 2. Let and be primes such that . Then and for every .
Another way of stating the claim would be in terms of expressions of the form where the are strictly increasing. What matters is simply to do justice to the informal idea that the product is “unique apart from the order”.
OK, let’s see what we can do with Claim 1.
2. See what you can say about a minimal counterexample.
When you first stare at the statement “ can be written as a product of primes” there seems to be nothing much to go on. Where do those primes come from? If you’re faced with a huge number that isn’t obviously a multiple of some small prime like 2, 3 or 5, then the following strategy for proving that it has a prime factorization fails miserably.
(i) Define some numbers in terms of .
(ii) Prove that all the are prime and that their product is equal to .
That’s the kind of strategy I might use if I wanted to find integers and such that and . I’d define to be and to be (these are the greatest integer that’s at most and the least integer that’s at least , respectively), and then I’d argue that and , probably by splitting into the cases where is odd and is even. But for finding some numbers that multiply together to give , it just doesn’t seem to work.
So what other options have we got? Our problem is that we don’t seem to have any information to use. But we can give ourselves a huge boost if we use one of the most fundamental techniques known to mathematicians, namely induction.
With that hint, you might be tempted to try the following strategy, which is, I’m afraid, still pretty hopeless.
(i) Assume that has a factorization into primes.
(ii) Attempt to prove that has a factorization into primes.
Why is this hopeless? Because the multiplicative structure of has nothing to do with the multiplicative structure of .
So why did I suggest induction? Because there are other forms of induction that do much better. One is to exploit the observation that if you are trying to prove the case, then you can, if you want, use not just the case but all previous cases. In our problem, we are free to assume that every positive integer less than can be factorized into primes. Aha, that looks as though it could be useful.
But why is it useful? How can we use prime factorizations of smaller numbers to obtain a prime factorization of ? There are two closely related ways that people often use. The first is simply to describe the method that we tend to use when finding prime factorizations of small numbers. We look for the smallest prime that goes into , then we divide by that and repeat the process.
The fact that I just said “and repeat the process” is a sign that to make the argument formal I should use induction. (Another phrase that also alerts us to that is “and so on”.) And indeed I can, as long as I use the strong form just mentioned. Here’s how the argument might go.
Proof 1.Let be a positive integer. If then we can write it as an “empty product” of primes. [This is not the important part of the proof.] Now let’s look for the smallest factor we can. There is no need to look for composite factors, since if is composite and then the factors of , which are smaller, also divide . Therefore, it suffices to check through all the primes, in increasing order. If we find a prime such that , then is a positive integer that’s smaller than , so it can be written in the form . But then . If we don’t find a prime , then has no non-trivial factors, which implies that is itself a prime.
In the course of writing that, we might notice that it didn’t really matter that was prime, since all we needed was a number that had a prime factorization. So here’s a shorter version of the same argument.
Proof 2. Let be a positive integer. If then it can be written as an empty product of primes. If and has no factors other than 1 and , then is prime. Otherwise, can be written as with both and strictly between 1 and . But then, by strong induction, we can assume that both and can be factorized into primes, from which it follows (putting the two factorizations together) that can as well.
The slogan that headed this section was “See what you can say about a minimal counterexample.” That is sort of what we were doing above. Here’s a way of making that more explicit. I’m using the well-ordering principle instead of induction.
Proof 3. Suppose that there is a positive integer with no prime factorization. Then there must be a least such positive integer, , say. Since empty products and primes themselves count as products of primes, must be composite, so let us write . Then by the minimality of , and can be written as products of primes, from which it follows that can be written as a product of primes, contradicting our initial assumption.
Although thinking about minimal counterexamples is great for coming up with proofs, I don’t actually like the argument that results in this case, since it doesn’t use the hypothesis that can’t be written as a product of primes in a strong way. The evidence for that is in Proof 2, which is essentially the same argument but with no need for any contradiction.
Right, that’s done existence. Let’s turn to uniqueness.
3. See what you can say about a minimal counterexample.
I did say that thinking about minimal counterexamples was good for coming up with arguments, so let’s see how we get on here. A counterexample to the uniqueness would be an equality of the form with the two sequences of primes not the same up to a permutation. What do we mean by a minimal counterexample? There’s a bit of choice here: we might mean that the number that equals both those products is as small as possible, but we might decide that we’re minimizing . As it happens, both choices work for what I want to say next, which is that we can see immediately that no prime can appear on both sides of the equation. Why not? Because if it did, then we could strike out that prime from both sides (by dividing by it) and we would have two smaller products that were still equal and still distinct sequences of primes. So we’ve got immediately that no is equal to any .
Now what? Having reduced to the case where no is equal to any we appear to be stuck: there is no longer any obvious way of making the example smaller.
It’s time for another standard proof-finding technique.
4. Identify the simplest case you can’t prove.
This is not a completely precise piece of advice, because problems don’t always split neatly into cases, and even if they do, they may do so in more than one way. Nevertheless, it often happens that a simplified version of a problem is easy enough that you can solve it, while also being difficult enough that the solution gives you important clues about how to prove the original problem.
What could count as a “case” of the problem we are trying to solve? Well, the problem we’re now thinking about asks us to show that a product of primes can never equal a product of entirely different primes. So an obvious “simple case” is to take and to be small.
The advice is to find the simplest case that we can’t prove. So let’s start with the simplest case we can, , and work up. Well, that’s a bit too simple, because we can’t have two distinct products of length 0. So how about ? That’s trivial: 1 is not equal to any prime. In fact, is trivial whatever is, so let’s try . That’s now asking us to prove that if and are distinct primes, then . I think we can manage that. How about . That’s asking us to show that if is a prime and and are primes not equal to , then . Still easy, since isn’t a prime. In fact, that argument shows that even is not interesting. So that brings us to . Is it obvious that if no is equal to any ?
If you’re inclined to answer yes at this point, then please read my previous post. It’s not obvious at all, and needs a proof.
Unfortunately, having identified the first case we can’t solve, we’re still stuck. Why shouldn’t equal ? How are we supposed to prove this?
It’s time for another standard proof-finding technique.
5. Identify the simplest case you can’t prove.
That’s not a misprint. We’ve got a new hard problem, so why not try the same technique again? After all, there is quite a simple way of generating special cases, even for this problem, since we can look at small primes.
Now I don’t mean by this the silly idea of seeing whether we can prove something like that . Whatever a “special case” is, it will need to be a general statement of some kind. The easiest way to achieve that is to let at least one of the primes be a variable. Now a moment’s reflection tells us that if we’ve got a fixed number on one side then it’s still not a suitable special case. For example, we can show that by simply observing that if then . That doesn’t feel as though it is telling us anything.
So let’s try showing that when and are distinct primes with and . Is that an easy problem? Yes it is, since is even and is odd (because is a prime not equal to 2).
Does that count as an informative proof? It’s a bit early to say, but it has the promising feature that it involves divisibility. It’s time for another proof-discovery technique.
6. If you manage to prove anything at all, then try to obtain the strongest result that follows from your proof method.
This general idea is the reason that looking at special cases is sometimes worth it. What was our proof? It was that is even, and is odd. But what did we use in order to prove that was odd? We used the fact that 3 is odd, that is odd, and that a product of two odd numbers is odd. Can we generalize our result?
Obviously yes, since if all we used about 3 was that it is odd, then we can replace 3 by any other odd prime. So a first generalization is that whenever and are odd primes. (The condition that they should not equal is not necessary — it just stops the problem being trivial.) But that’s not all we can do. The result that a product of two odd numbers is odd has an easy generalization to the result that a product of any number of odd numbers is odd. So if we use that, then we obtain the result that whenever are odd primes.
Have we finished? No we haven’t, since all we needed about the left-hand side was that it was even. So we can replace by an arbitrary product of primes. That means that we have proved the general result we are trying to prove — that — provided that .
Now have we finished? Well, we’ve managed to prove the whole result when one of the primes is equal to 2. Can we use the same method for other primes? What would be required?
Well, the fact that drove the entire argument was this: a product of two odd numbers is an odd number, which implies that a product of any number of odd numbers is an odd number. What would be the corresponding fact we would have to use when is a general prime?
The two numbers we want to be distinct are and . What is the analogue for a general of the concept of evenness? It is divisibility by . So if we want to copy the argument that worked when , we should start by observing that is divisible by and we should aim to prove that is not divisible by . What information do we have to go on? We know that no is equal to any , but if we bear in mind what we did when we will expect that all that really matters is that no is equal to .
So now we’ve reduced our problem to the following. If none of is equal to , then is not a multiple of . And if we want to be a bit bolder, we could spot that when we didn’t even use the fact that the were prime — we just used the fact that they were odd. So we might expect that the right thing to try to prove is that if all the are positive integers and none of them is a multiple of , then is not a multiple of .
An advantage of this final formulation is that it follows straightforwardly from the case . That is, we will be done if we can prove the following result: whenever and are non-multiples of , then so is . Turning to the contrapositive, and forgetting the suffix 1, which is no longer playing a useful role, we find that the fundamental theorem of arithmetic is reduced to the following statement.
Claim. Let be a prime and let be positive integers such that . Then or .
However, this statement itself does not seem all that easy to prove, so it’s time to go back to our favourite method for getting an idea. Here it is again.
7. Identify the simplest case you can’t prove.
A natural notion of “case” is obtained if we think about what prime we are talking about. We’ve already done the case , so how about the case ? If and are non-multiples of 3, does it follow that is a non-multiple of 3? Yes it does, and here’s a quick reason for that. Let’s consider what and are mod 3. Since they are non-multiples of 3, they are both equal either to 1 or to 2. But , so we never get a multiple of 3.
Note that that was a generalization of the proof that a product of odd numbers is odd, which is encouraging. Indeed, if you stop to think about it, you’ll see that for any given prime , there is in principle a proof of what we want: you just calculate the multiplication table mod and check that there are no non-trivial zero divisors.
A bit less encouraging is that as gets bigger, the proof you write down gets longer. What’s more, it doesn’t give us any insight into why the result is true: we just work out the multiplication table, keeping our fingers crossed that we won’t find zero divisors. What is lacking is any pattern to the results, or a general reason for the divisors not to exist.
8. Try to draw analogies with other contexts.
Maybe by this stage you know what to do: if you know the proof that there are no non-trivial zero divisors mod , then you are finished. But suppose you didn’t know. Then you might once again have that stuck feeling. Another good way of getting out of that situation is to look at similar problems where you do know what to do. (This is an incredibly important method used in mathematical research — I’m tempted to say that it is the most important method we have.)
What, then, does the phrase “no zero divisors” suggest to you? Perhaps the familiar result that if and are two non-zero real numbers, then is also non-zero. How do we prove that? We say that if is zero, and if is not zero, then we can divide both sides by and deduce that .
OK, back to what we’re actually trying to prove. We’ve got two numbers and such that mod and would like to deduce that either mod or mod . The real-number result suggests that we should try to divide both sides of by (unless ). Can we do that? Well, we don’t exactly have division, so let’s think a bit further.
What is division of real numbers? The simplest way of defining it is perhaps this. First, we establish that every non-zero real number has a multiplicative inverse (or reciprocal), and then we define to be mutliplied by the inverse of .
This way of looking at things gives us something we can take back to the mod- context. We start with the assumption that mod . We’d now like to multiply both sides of this equation by a multiplicative inverse of , assuming such a thing exists. If we can find such that mod , then from the fact that we will be able to deduce that .
So now the whole thing has boiled down to the statement that if mod then there exists some such that mod .
Just before we continue, I want to stress that we have actually done something here. Sometimes a reformulation of a statement produces a new statement that is so obviously equivalent to the original statement that it doesn’t get you any closer to proving it. An example would be what we did a little earlier when we reformulated this
That achieves almost nothing, because and mod are basically the same statement. However, it does give us a nudge in the direction of the next reformulation, which is genuinely different.
This last reformulation is different because it gives us a strategy for showing that mod . Once we’ve come up with this useful number , we’ll be done.
But how do we come up with ?
9. If there’s another way of looking at something, then even if it isn’t a substantial reformulation, it may make the problem easier to think about.
In this case, we could try translating back from mod- language to ordinary integer language. Here’s the reformulation that results.
Hmm … that last bit doesn’t feel like enough of a reformulation. What does it mean to say that leaves a remainder of 1 when you divide by ? It means that is 1 more than a multiple of . So let’s tidy up the latest reformulation.
10. If anything you see reminds you of anything you know, then pounce.
We’re given two integers and , about which we know that is prime and is not a multiple of . We are trying to find and such that . Does this look like anything we’ve seen before? Yes it does. It’s very similar to Bézout’s theorem. Indeed, if we replace by , then our task is to solve the equation , and Bézout’s theorem tells us we can do this as long as . But is prime, so has to be 1 or . Since it’s not (by assumption) it must be 1, and we are done.
That’s a proof discovery process assuming you already know Bézout’s theorem. But note that the process did not start with the hint, “By the way, Bézout’s theorem is useful.” Rather, the need for Bézout’s theorem arose naturally. So even if you don’t know Bézout’s theorem, at least you can still arrive at the statement of the theorem and recognise that once you’ve proved it you can deduce the fundamental theorem of arithmetic.
What about Bézout’s theorem though? How might you come up with a proof of that? There are many possible ways — I’ll describe one.
Let’s revisit one of the recent problem-solving tips.
11. If there’s another way of looking at something, then even if it isn’t a substantial reformulation, it may make the problem easier to think about.
OK, we’ve got a prime and a number that is not congruent to 0 mod . We are trying to find a multiplicative inverse for mod . That is, we are trying to solve the equation .
But let’s remember why we were trying to find . The reason was that we wanted a cancellation law. That is, we wanted to be able to say that if then , or rather we wanted to be able to do that in the special case where and . (It was a bit silly to call a “special case”, since is arbitrary, but let’s not worry about that. Certainly, restricting to is a special case.)
Now let’s see whether makes us think of anything. It certainly should if you’ve read and digested the post in this series about properties of functions. It looks very like the definition of an injection. In fact, it is the definition of an injection for the function that takes to (where I’m thinking of and as elements of the group of integers mod ).
Let’s denote this group by . We’ve just defined a function by setting . In this terminology, our aim is to prove that is an injection.
Now injections from finite sets to themselves have a remarkable property, though you may not find it all that remarkable: they are also surjections. To see that this statement is saying at least something, note that it is quite clearly false for infinite sets. For instance, the function that takes to is an injection from to that never takes the value 1. Informally, the reason it is true for finite sets is that if is finite and is an function, then the only way that can send distinct elements to distinct elements is if it uses up the whole of as its image. Equivalently, there is no injection from to for any positive integer . To prove this formally is a good exercise in the use of induction, though it may well have been a lemma in the course. And you should be able to deduce easily from this result that if is finite and then all the three properties “is an injection”, “is a surjection” and “is a bijection” are equivalent.
When an equivalence is true but not completely trivial to prove, it is almost always useful. Here, it doesn’t seem to get us anywhere. After all, we started by wanting to show that we can find such that and have ended up by saying that it will be enough to prove that the function that takes to (which equals ) is a surjection. Well, of course that will be enough! We want to prove that it takes the value 1 — it surely doesn’t make our task easier to show that it takes all possible values.
That, however, is not a valid argument. Often it is easier to prove a stronger result, because you have less room for manoeuvre, and the less choice you have about what to do, the easier it is to work out what to do. It’s a bit like having only one way of getting out of check: whatever the disadvantages may be, at least there is no problem working out what your best move is. And here we know that it isn’t a real disadvantage because we’ve managed to establish, for our particular function, that it takes the value 1 somewhere if and only if it is a surjection.
That still doesn’t really give us much idea of why it could be advantageous to go for the stronger-looking statement. One reason is that it leads us naturally to the following line of thought. We are trying to prove something about the image of the function (the function from to that takes to ). The statement we want to prove is that the image of is the whole of , but instead of trying to do that all in one go, let’s use another problem-solving strategy.
12. If you don’t immediately see why an object has a certain property, then just see what you can say about that object: it may help.
What can we say about the image of ? We can write it down if we want: it’s the set , where all those numbers are to be interpreted mod . In other words, it’s the set of all multiples of .
We don’t at this point know that all those numbers are distinct mod , or we’d have our injection/surjection, but what can we say about the set? Well, it’s obviously closed under addition mod — if you add two multiples of together you’ll get another one. But hang on, forms a group under addition mod and we’ve got a subset that’s closed under addition. Could it be a subgroup? Indeed it could: the inverse of is so it’s closed under taking inverses as well. (You may have had it pointed out to you that for subsets of finite groups it’s enough to show that they are closed under the group operation: you can get the inverse of by finding such that and taking .)
But the group is cyclic of prime order, and we know all about subgroups of those: they are trivial. Why? Because Lagrange’s theorem tells us they must have size 1 or , and that forces them to be or . Since , it follows that the set of multiples of , or equivalently the subgroup generated by , is the whole of .
As I hope you’ve seen, we’re done. We’ve just shown that the image of the map is the whole of , which tells us that it’s a surjection, which tells us that it’s an injection, which tells us that we have the cancellation law, which tells us that if and , then .
It’s possible to give other accounts of how one might arrive at a proof of the fundamental theorem of arithmetic. Indeed, I wrote one myself several years ago that is similar to this one up to the point of formulating the lemma that if then divides one of and , but that diverges from it thereafter, ending up with the more usual proof via Euclid’s algorithm. (I deliberately didn’t read that one before writing this, and I find it quite interesting to see how similar much of what I’ve written now is to what I wrote then.)
I worry sometimes that accounts like this of how a proof might be discovered can be off-puttingly long. So it’s important to stress that the actual proofs are much much shorter. Here’s how the proof that the above thoughts lead to ends up. I’ll just do the uniqueness part, and I’ll write the whole thing in logical order, which is more or less the reverse of the order in which one discovers the steps.
Proof that prime factorizations are unique.
Lemma 1. Let be a prime and let be an integer not congruent to mod . Then the equation mod has a solution.
Proof. Define a function by . Then the image of is a subgroup of (since is a homomorphism). Since it contains , it is not the subgroup , so by Lagrange’s theorem it must be all of . In particular, it contains 1.
Corollary 2. Let be a prime and let and be integers such that . Then or .
Proof. If is not a multiple of then by Lemma 1 we can find such that mod . It follows that .
Corollary 3. Let be a prime and let be integers such that . Then there exists such that .
Proof. Induction on . We’ve proved it if . For larger we know by the case that either or . In the second case we are done and in the first case we are done by induction.
Proof of uniqueness. Suppose that , that the two products are not the same even after reordering, and that and are minimal such that this can be done. Then no can equal any , or we could divide through and get an example with and .
Since the are prime, it follows that does not divide any of them. But then, by Corollary 3, it does not divide their product . But it does divide , contradicting the assumption that the two products are equal.