Proving the fundamental theorem of arithmetic

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 $p|ab$ then either $p|a$ or $p|b$ , 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 $n$ be a positive integer. Then there exists a sequence $(p_1,\dots,p_r)$ of prime numbers such that $p_1p_2\dots p_r=n$ .

Claim 2. Let $(p_1,\dots,p_r)$ and $(q_1,\dots,q_s)$ be two sequences of primes and suppose that $p_1\dots p_r=q_1\dots q_s$ . Then $r=s$ and there is a permutation $\sigma$ of $\{1,2,\dots,r\}$ such that $q_i=p_{\sigma(i)}$ for every $i\in\{1,2,\dots,r\}$ .

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 $p_1\leq p_2\leq\dots\leq p_r$ and $q_1\leq q_2\leq\dots\leq q_s$ be primes such that $p_1\dots p_r=q_1\dots q_s$ . Then $r=s$ and $p_i=q_i$ for every $i\in\{1,2,\dots,r\}$ .

Another way of stating the claim would be in terms of expressions of the form $p_1^{a_1}\dots p_r^{a_r}$ where the $p_i$ 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 “ $n$ 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 $n$ 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 $p_1,\dots,p_k$ in terms of $n$ .

(ii) Prove that all the $p_i$ are prime and that their product is equal to $n$ .

That’s the kind of strategy I might use if I wanted to find integers $a$ and $b$ such that $a+b=n$ and $|a-b|\leq 1$ . I’d define $a$ to be $\lfloor n/2\rfloor$ and $b$ to be $\lceil n/2\rceil$ (these are the greatest integer that’s at most $n/2$ and the least integer that’s at least $n/2$ , respectively), and then I’d argue that $|a-b|\leq 1$ and $a+b=n$ , probably by splitting into the cases where $n$ is odd and $n$ is even. But for finding some numbers that multiply together to give $n$ , 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 $n-1$ has a factorization into primes.

(ii) Attempt to prove that $n$ has a factorization into primes.

Why is this hopeless? Because the multiplicative structure of $n$ has nothing to do with the multiplicative structure of $n-1$ .

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 $n$ case, then you can, if you want, use not just the $n-1$ case but all previous cases. In our problem, we are free to assume that every positive integer less than $n$ 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 $n$ ? 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 $n$ , 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 $n$ be a positive integer. If $n=1$ 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 $a$ is composite and $a|n$ then the factors of $a$ , which are smaller, also divide $n$ . Therefore, it suffices to check through all the primes, in increasing order. If we find a prime $p$ such that $p|n$ , then $n/p$ is a positive integer that’s smaller than $n$ , so it can be written in the form $p_1p_2\dots p_r$ . But then $n=pp_1\dots p_r$ . If we don’t find a prime $p$ , then $n$ has no non-trivial factors, which implies that $n$ is itself a prime. $\square$

In the course of writing that, we might notice that it didn’t really matter that $p$ 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 $n$ be a positive integer. If $n=1$ then it can be written as an empty product of primes. If $n\geq 2$ and $n$ has no factors other than 1 and $n$ , then $n$ is prime. Otherwise, $n$ can be written as $ab$ with both $a$ and $b$ strictly between 1 and $n$ . But then, by strong induction, we can assume that both $a$ and $b$ can be factorized into primes, from which it follows (putting the two factorizations together) that $n$ can as well. $\square$

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, $n$ , say. Since empty products and primes themselves count as products of primes, $n$ must be composite, so let us write $n=ab$ . Then by the minimality of $n$ , $a$ and $b$ can be written as products of primes, from which it follows that $n$ can be written as a product of primes, contradicting our initial assumption. $\square$

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 $n$ 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 $p_1\dots p_r=q_1\dots q_s$ 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 $n$ that equals both those products is as small as possible, but we might decide that we’re minimizing $r$ . 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 $p_i$ is equal to any $q_j$ .

Now what? Having reduced to the case where no $p_i$ is equal to any $q_j$ 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 $r$ primes can never equal a product of $s$ entirely different primes. So an obvious “simple case” is to take $r$ and $s$ 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, $r=s=0$ , and work up. Well, that’s a bit too simple, because we can’t have two distinct products of length 0. So how about $r=0,s=1$ ? That’s trivial: 1 is not equal to any prime. In fact, $r=0$ is trivial whatever $s$ is, so let’s try $r=1,s=1$ . That’s now asking us to prove that if $p$ and $q$ are distinct primes, then $p\ne q$ . I think we can manage that. How about $r=1,s=2$ . That’s asking us to show that if $p$ is a prime and $q_1$ and $q_2$ are primes not equal to $p$ , then $p\ne q_1q_2$ . Still easy, since $q_1q_2$ isn’t a prime. In fact, that argument shows that even $r=1$ is not interesting. So that brings us to $r=2,s=2$ . Is it obvious that $p_1p_2\ne q_1q_2$ if no $p_i$ is equal to any $q_j$ ?

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 $p_1p_2$ equal $q_1q_2$ ? 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 $2\times 2\ne 3\times 3$ . 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 $2\times 2\ne 3\times q$ by simply observing that if $q\ne 2$ then $3q>4$ . That doesn’t feel as though it is telling us anything.

So let’s try showing that $2p\ne 3q$ when $p$ and $q$ are distinct primes with $p\ne 3$ and $q\ne 2$ . Is that an easy problem? Yes it is, since $2p$ is even and $3q$ is odd (because $q$ 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 $2p$ is even, and $3q$ is odd. But what did we use in order to prove that $3q$ was odd? We used the fact that 3 is odd, that $q$ 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 $2p\ne q_1q_2$ whenever $q_1$ and $q_2$ are odd primes. (The condition that they should not equal $p$ 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 $2p\ne q_1q_2\dots q_s$ whenever $q_1,\dots,q_s$ 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 $p$ by an arbitrary product of primes. That means that we have proved the general result we are trying to prove — that $p_1\dots p_r\ne q_1\dots q_s$ — provided that $p_1=2$ .

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 $p_1$ is a general prime?

The two numbers we want to be distinct are $p_1\dots p_r$ and $q_1\dots q_s$ . What is the analogue for a general $p_1$ of the concept of evenness? It is divisibility by $p_1$ . So if we want to copy the argument that worked when $p_1=2$ , we should start by observing that $p_1\dots p_r$ is divisible by $p_1$ and we should aim to prove that $q_1\dots q_s$ is not divisible by $p_1$ . What information do we have to go on? We know that no $p_i$ is equal to any $q_j$ , but if we bear in mind what we did when $p_1=2$ we will expect that all that really matters is that no $q_j$ is equal to $p_1$ .

So now we’ve reduced our problem to the following. If none of $q_1,\dots,q_s$ is equal to $p_1$ , then $q_1\dots q_s$ is not a multiple of $p_1$ . And if we want to be a bit bolder, we could spot that when $p_1=2$ we didn’t even use the fact that the $q_i$ 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 $q_i$ are positive integers and none of them is a multiple of $p_1$ , then $q_1\dots q_s$ is not a multiple of $p_1$ .

An advantage of this final formulation is that it follows straightforwardly from the case $s=2$ . That is, we will be done if we can prove the following result: whenever $a$ and $b$ are non-multiples of $p_1$ , then so is $ab$ . 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 $p$ be a prime and let $ab$ be positive integers such that $p|ab$ . Then $p|a$ or $p|b$ .

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 $p=2$ , so how about the case $p=3$ ? If $a$ and $b$ are non-multiples of 3, does it follow that $ab$ is a non-multiple of 3? Yes it does, and here’s a quick reason for that. Let’s consider what $a$ and $b$ are mod 3. Since they are non-multiples of 3, they are both equal either to 1 or to 2. But $1\times 1=2\times 2\equiv 1,$ $1\times 2=2\times 1\equiv 2$ , 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 $p$ , there is in principle a proof of what we want: you just calculate the multiplication table mod $p$ and check that there are no non-trivial zero divisors.

A bit less encouraging is that as $p$ 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 $p$ , 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 $x$ and $y$ are two non-zero real numbers, then $xy$ is also non-zero. How do we prove that? We say that if $xy$ is zero, and if $x$ is not zero, then we can divide both sides by $x$ and deduce that $y=0$ .

OK, back to what we’re actually trying to prove. We’ve got two numbers $a$ and $b$ such that $ab\equiv 0$ mod $p$ and would like to deduce that either $a\equiv 0$ mod $p$ or $b\equiv 0$ mod $p$ . The real-number result suggests that we should try to divide both sides of $ab\equiv 0$ by $a$ (unless $a\equiv 0$ ). 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 $x/y$ to be $x$ mutliplied by the inverse of $y$ .

This way of looking at things gives us something we can take back to the mod- $p$ context. We start with the assumption that $ab\equiv 0$ mod $p$ . We’d now like to multiply both sides of this equation by a multiplicative inverse of $a$ , assuming such a thing exists. If we can find $c$ such that $ca\equiv 1$ mod $p$ , then from the fact that $ab\equiv 0$ we will be able to deduce that $b\equiv 1b\equiv cab\equiv c0\equiv 0$ .

So now the whole thing has boiled down to the statement that if $a\not\equiv 0$ mod $p$ then there exists some $c$ such that $ca\equiv 1$ mod $p$ .

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

Let $p$ be a prime number and let $a$ and $b$ be positive integers. Then if $p|ab$ it follows that $p|a$ or $p|b$ .

as this

Let $p$ be a prime number and let $a$ and $b$ be positive integers such that $ab\equiv 0$ mod $p$ . Then either $a\equiv 0$ mod $p$ or $b\equiv 0$ mod $p$ .

That achieves almost nothing, because $p|n$ and $n\equiv 0$ mod $p$ are basically the same statement. However, it does give us a nudge in the direction of the next reformulation, which is genuinely different.

Let $p$ be a prime number and let $a$ be a positive integer such that $a\not\equiv 0$ mod $p$ . Then there exists $c$ such that $ca\equiv 1$ mod $p$ .

This last reformulation is different because it gives us a strategy for showing that $b\equiv 0$ mod $p$ . Once we’ve come up with this useful number $c$ , we’ll be done.

But how do we come up with $c$ ?

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- $p$ language to ordinary integer language. Here’s the reformulation that results.

Let $p$ be a prime number and let $a$ be a positive integer that is not a multiple of $p$ . Show that there is an integer $c$ such that $ca$ leaves a remainder of 1 when you divide by $p$ .

Hmm … that last bit doesn’t feel like enough of a reformulation. What does it mean to say that $ca$ leaves a remainder of 1 when you divide by $p$ ? It means that $ca$ is 1 more than a multiple of $p$ . So let’s tidy up the latest reformulation.

Let $p$ be a prime number and let $a$ be a positive integer that is not a multiple of $p$ . Show that there is an integer $c$ and another integer $m$ such that $ca=mp+1$ .

10. If anything you see reminds you of anything you know, then pounce.

We’re given two integers $a$ and $p$ , about which we know that $p$ is prime and $a$ is not a multiple of $p$ . We are trying to find $c$ and $m$ such that $ca=mp+1$ . 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 $m$ by $-m$ , then our task is to solve the equation $ca+mp=1$ , and Bézout’s theorem tells us we can do this as long as $(a,p)=1$ . But $p$ is prime, so $(a,p)$ has to be 1 or $p$ . Since it’s not $p$ (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 $p$ and a number $a$ that is not congruent to 0 mod $p$ . We are trying to find a multiplicative inverse for $a$ mod $p$ . That is, we are trying to solve the equation $ca\equiv 1$ .

But let’s remember why we were trying to find $c$ . The reason was that we wanted a cancellation law. That is, we wanted to be able to say that if $ax\equiv ay$ then $x\equiv y$ , or rather we wanted to be able to do that in the special case where $x=b$ and $y=0$ . (It was a bit silly to call $x=b$ a “special case”, since $b$ is arbitrary, but let’s not worry about that. Certainly, restricting to $y=0$ is a special case.)

Now let’s see whether $ax=ay\implies x=y$ 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 $x$ to $ax$ (where I’m thinking of $x$ and $ax$ as elements of the group of integers mod $p$ ).

Let’s denote this group by $\mathbb{Z}_p$ . We’ve just defined a function $f:\mathbb{Z}_p\to\mathbb{Z}_p$ by setting $f(x)=ax$ . In this terminology, our aim is to prove that $f$ 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 $n$ to $n+1$ is an injection from $\mathbb{N}$ to $\mathbb{N}$ that never takes the value 1. Informally, the reason it is true for finite sets is that if $X$ is finite and $f:X\to X$ is an function, then the only way that $f$ can send distinct elements to distinct elements is if it uses up the whole of $X$ as its image. Equivalently, there is no injection from $\{1,2,\dots,n\}$ to $\{1,2,\dots,n-1\}$ for any positive integer $n$ . 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 $X$ is finite and $f:X\to X$ 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 $c$ such that $ca\equiv 1$ and have ended up by saying that it will be enough to prove that the function that takes $x$ to $ax$ (which equals $xa$ ) 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 $f$ (the function from $\mathbb{Z}_p$ to $\mathbb{Z}_p$ that takes $x$ to $ax$ ). The statement we want to prove is that the image of $f$ is the whole of $\mathbb{Z}_p$ , 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 $f$ ? We can write it down if we want: it’s the set $\{0,a,2a,3a,\dots,(p-1)a\}$ , where all those numbers are to be interpreted mod $p$ . In other words, it’s the set of all multiples of $a$ .

We don’t at this point know that all those numbers are distinct mod $p$ , or we’d have our injection/surjection, but what can we say about the set? Well, it’s obviously closed under addition mod $p$ — if you add two multiples of $a$ together you’ll get another one. But hang on, $\mathbb{Z}_p$ forms a group under addition mod $p$ and we’ve got a subset that’s closed under addition. Could it be a subgroup? Indeed it could: the inverse of $ra$ is $(p-r)a$ 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 $g$ by finding $r$ such that $g^r=e$ and taking $g^{r-1}$ .)

But the group $\mathbb{Z}_p$ 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 $p$ , and that forces them to be $\{0\}$ or $\mathbb{Z}_p$ . Since $a\not\equiv 0$ , it follows that the set of multiples of $a$ , or equivalently the subgroup generated by $a$ , is the whole of $\mathbb{Z}_p$ .

As I hope you’ve seen, we’re done. We’ve just shown that the image of the map is the whole of $\mathbb{Z}_p$ , 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 $ab\equiv 0$ and $a\not\equiv 0$ , then $b\equiv 0$ .

Conclusion.

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 $p|ab$ then $p$ divides one of $a$ and $b$ , 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 $p$ be a prime and let $a$ be an integer not congruent to $0$ mod $p$ . Then the equation $ax\equiv 1$ mod $p$ has a solution.

Proof. Define a function $f:\mathbb{Z}_p\to\mathbb{Z}_p$ by $f(x)=ax$ . Then the image of $f$ is a subgroup of $\mathbb{Z}_p$ (since $f$ is a homomorphism). Since it contains $a$ , it is not the subgroup $\{0\}$ , so by Lagrange’s theorem it must be all of $\mathbb{Z}_p$ . In particular, it contains 1. $\square$

Corollary 2. Let $p$ be a prime and let $a$ and $b$ be integers such that $p|ab$ . Then $p|a$ or $p|b$ .

Proof. If $a$ is not a multiple of $p$ then by Lemma 1 we can find $c$ such that $ca\equiv 1$ mod $p$ . It follows that $b\equiv (ca)b\equiv c(ab)\equiv 0$ . $\square$

Corollary 3. Let $p$ be a prime and let $a_1,\dots,a_k$ be integers such that $p|a_1\dots a_k$ . Then there exists $i$ such that $p|a_i$ .

Proof. Induction on $k$ . We’ve proved it if $k=2$ . For larger $k$ we know by the $k=2$ case that either $p|a_1\dots a_{k-1}$ or $p|a_k$ . In the second case we are done and in the first case we are done by induction. $\square$

Proof of uniqueness. Suppose that $p_1\dots p_r=q_1\dots q_s$ , that the two products are not the same even after reordering, and that $r$ and $s$ are minimal such that this can be done. Then no $p_i$ can equal any $q_j$ , or we could divide through and get an example with $r-1$ and $s-1$ .

Since the $q_j$ are prime, it follows that $p_1$ does not divide any of them. But then, by Corollary 3, it does not divide their product $q_1\dots q_s$ . But it does divide $p_1\dots p_r$ , contradicting the assumption that the two products are equal. $\square$

This entry was posted on November 18, 2011 at 11:47 pm and is filed under Cambridge teaching, IA Numbers and Sets. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.

31 Responses to “Proving the fundamental theorem of arithmetic”

Fabian Says:
November 19, 2011 at 12:22 am | Reply
Amann/Escher’s “Analysis 1” has a proof that uses a simple minimal counterexample argument to prove the uniqueness part without induction / Bezout / “p|ab => p|a or p|b”:

http://books.google.de/books?id=on6GoQjmHC0C&pg=PA36&dq=%22prime+factorization%22

(Page 36, Proposition 5.6, in case the link doesn’t work)
Marc Says:
November 19, 2011 at 5:24 am | Reply
Great post.

Regarding your concern that going through the thought process of the proof might be too long, I’d like to say that I would have wished for more along these lines when I did the Tripos (2004-2008). While it is sometimes really a bit painful, I find I get a lot more out of why someone thought of an idea than out of a slick proof that starts off by some Deus ex Machina that of course no sane person would ever have thought off initially.

Thanks for putting these posts up.
John Baez Says:
November 19, 2011 at 8:26 am | Reply
Here we can see you think about math, and also think about how you think about math. But to do that so well, I bet you also had to think about how you think about how you think about math.
- gowers Says:
  November 19, 2011 at 9:11 am
  I’ll have to think about that …
garciacuervaGarcía-Cuerva Says:
November 19, 2011 at 9:50 am | Reply
The proof Fabian mentions is the one contained in Courant-Robbins (“What is mathematics?”, 1941). It appears also in the book “Lectures on elementary number theory” by Hans Rademacher (1964), where it is attributed to Hasse, the physicist F. A. Lindemann (later Lord Cherwell) and Zermelo.
Jason Dyer Says:
November 21, 2011 at 7:57 pm | Reply
I converted a wordier version of the proof Fabian mentions from an elementary text of Niven into a demonstration of fancy design in math notation
uwe Says:
November 22, 2011 at 2:28 am | Reply
Nicely explained. For the last part (p | ab => p | a v p | b), couldn’t you just go to gcd and Euclidean algorithm ? It’s probably more familiar to people than Lagrange’s theorem.
- gowers Says:
  November 22, 2011 at 2:55 pm
  That was (at least implicitly) the first approach I suggested: you reduce the problem to Bézout’s theorem, which is normally proved using Euclid’s algorithm, or, more or less equivalently, the argument that starts with the smallest integer combination of the two numbers you’re given. One of the things I’m trying to do in these posts is emphasize how much choice there is about how you prove things, or how you explain your proofs of things, so when it occurred to me that Lagrange’s theorem could be used I decided to give that argument instead. The more traditional approach can be found in the account I linked to in the second line of the concluding section above.
Expository Articles | Thinking Aloud :: CS Education Says:
November 22, 2011 at 6:03 am | Reply
[…] Often we look at a sleek proof and wonder how someone could have come up with it. Expositions that demystify the problem solving process the are extremely rare, even in educational articles. That’s why you should take a look at this excellent piece by Gowers’ on how to prove, (or rather how you could have proved) the fundamental theorem of arithmetic. […]
Joseph Says:
November 22, 2011 at 11:25 pm | Reply
I found the proof using Bézout’s theorem quite unmotivated when I learned it – it seemed to be a clever trick that you just had to think of. The perspective of finding a multiplicative inverse $mod p$ is much clearer and I had never realised the relationship between the two statements (fundamental theorem of arithmetic and existence of inverses) before.

It is perhaps a minor notational point, but I find it easier to think of your chain of congruences in corollary 2 as a modification of the congruence $ab \equiv 0$ by left multiplication by $c$ . That is, in my mental image of this part of the proof, we start off with this congruence, and it is modified to $b \equiv 0$ . We have a sequence of mental images with rules (or mental machinery) for progressing from one to the next. Alternatively, I have to look at the each congruence in the chain in order and try to think of a reason why it’s true and I feel my picture of what’s going on isn’t as good.
Peter Gerdes Says:
November 23, 2011 at 2:21 pm | Reply
Whoa you hide all the real work inside Lagrange’s theorem. That’s really no fair since it’s at root a combinatorial argument.

I’d prefer something like this: suppose \alpha \neq 0 is a zero divisor in Z_p. Consider the mapping f:Z_p -> G = {\alpha x for x in Z_p}. Clearly the image of this map is a group under + and it must be of strictly smaller order than Z_p since f isn’t injective as f(0)=f(\alpha*x). Now consider the equivalence relation on Z_p given by x ~ y iff x- y = \alpha *z for some z in 0…p-1. Now given an equivalence classes E_x the map g: E_x -> E_y defined by g(z)=z-x+y is surjective as given w \in E_y w -y =\alpha * r so g(\alpha*r +x) = w and injective as if g(z_1) = g(z_2) then z_1 -x +y = z_2 -x +y in Z_p so z_1=z_2 in Z_p. Let the size of an equivalence class be k as they all have the same size and note that k is the size of G as E_0 = G. Now the sum of the sizes of the equivalence classes must be p so r*k = p but k \neq 1 and k \neq p contradicting the primality of p. Hence \alpha \neq 0 is not a zero divisor. Hence if ab = 0 mod p either a = 0 mod p or b = 0 mod p.

But this isn’t real math this is formal crap. Real math just handwaves to get results. If you want a formally valid proof go look at the computer generated stuff since the goal of mathematics is to generate results we are confident in not formal proofs.

As an aside I once did a talk back in school just presenting sketches of something like 10 different proofs there were an infinite number of primes. Amazing the kind of elegant proofs you can get from weird topologies or even analysis.
Peter Gerdes Says:
November 23, 2011 at 2:23 pm | Reply
Also it seems to me this can only confuse new mathematicians.

The proof of the fundamental theorem of arithmetic is easy because you don’t tackle the whole formal ball game at once. Rather you start with the claim you want to prove and gradually reduce it to ‘obviously’ true lemmas like the p | ab thing. Then you search for proofs to those.
Weekly Picks « Mathblogging.org — the Blog Says:
November 24, 2011 at 2:19 pm | Reply
[…] some “extended” slides from a talk on diffusion in the Ehrenfest wind-tree model. Gowers’s Weblog gave an insight into how to think mathematics while proving the fundamental theorem of arithmetic. […]
Boaz Says:
November 24, 2011 at 8:34 pm | Reply
Personally, I’d prefer an “algorithmic” description of this proof. This is the same proof, but just motivated by the general principle of “if you’re trying to prove that something exists, think of an algorithm that produces it” (and to show uniqueness, show that any other solution is equal to that produced by the algorithm).

In this case, there is the natural algorithm A (which you mentioned in a previous post) that given a number n produces its factorization, by finding the smallest prime p that divides n, outputting it, and continuing with n/p . So, another way to state the theorem is:

Claim 1 (existence): For all n, A(n) is indeed a factorization of n.

Claim 2 (uniqueness): If n = p_1…p_k with p_1<= … <= p_k then A(n) = (p_1,….,p_k)

The inductive proof of Claim 1 is easy. To prove Claim 2 by induction, you need to prove that for n as above, if p< p_1 then p does not divide n. To do this what you need to prove is your Corollary 2 that if p|ab then p|a or p|b (here a=p_1 and b=p_2…p_k, and p does not divide p_1 since they're distinct primes, and you can prove that p does not divide p_2….p_k by induction).

This gives motivation to the statement of Corollary 2 but then one of course needs to prove it, either by the g.c.d algorithm or as you did it.
Donkey_2009 Says:
November 25, 2011 at 6:14 pm | Reply
I love the way you have broken the proof up into its component ‘Tricks’. I see that you have recently been considering creating articles for proofs on the Tricki, and this seems like an ideal candidate for the first such article, as it is a simple exposition of several ‘Tricks’. See my post on the Tricki forum for more of my ideas.
ogerard Says:
November 26, 2011 at 1:11 pm | Reply
Dear Prof. Gowers.

Thanks for this long and detailed post. It is not customary that mathematicians publish an analysis (in the greek sense of the word) of a particular result, even an ancient one, only a synthesis in the form of a proof.

The way you present this proof has a few drawbacks but has among its advantages a preparation for the related results in algebraic number theory and ideal theory of rings.

I feel you should point out the relation of Lagrange’s theorem with associativity of multiplication.

NB: I think you forgot to use the congruence sign (and mod p) in the statement of lemma 1 at the start of your synthesis of the proof (at the end of your post).
- gowers Says:
  November 26, 2011 at 3:06 pm
  I didn’t exactly forget the congruence sign — it’s more that I was “thinking mod $p$ “, so to speak. However, I’ve changed it in the interests of clarity.
  
  I’m afraid I don’t know what mathematical point you are referring to when you talk about Lagrange’s theorem and associativity — can you elaborate slightly?
Dean Menezes Says:
December 26, 2011 at 4:26 am | Reply
I think what ogerard is referring to when he says that Lagrange’s theorem is related to associativity of multiplication is that in the proof of Lagrange’s theorem, you consider the main group G whose underlying set consists of elements a,b,c,d,etc. and the subgroup E.
The sets aE, bE, cE, dE, etc. either are the same set or are distinct. This is equivalent to saying that the property of being in the same set is an equivalence relation. Then the transitivity property is proven by means of the associative property of multiplication.
How proofs happen « A blog of small things Says:
April 26, 2012 at 7:41 am | Reply
[…] this description of how to prove the Fundamental Theorem of Arithmetic (that every number has a unique factorization into prime numbers) is invaluable. It describes how […]
Fundamental theorem of arithmetic » Zyymat: Mathematics Says:
October 3, 2012 at 9:35 pm | Reply
[…] Gower 写了两篇关于此定理的博客文章: Why isn’t the fundamental theorem of arithmetic obvious? 和 Proving the fundamental theorem of arithmetic. […]
jack Says:
January 16, 2015 at 12:58 pm | Reply
Why is $f(x)=ax$ a group homomorphism in the proof of Lemma 1? I don’t get $a(xy)=axay$ . Do I miss something?
- gowers Says:
  January 17, 2015 at 4:19 pm
  The group in question is $\mathbb{Z}_p$ under addition, not multiplication.
Jack Says:
January 16, 2015 at 2:53 pm | Reply
Dear Prof. Gowers,

In the proof of lemma 1, the image of $f$ is indeed a subgroup of $\bf{Z}_p$ as you’ve shown in the second paragraph right after slogan 12. But I don’t think it is because “ $f$ is a homomorphism”.
anon Says:
April 8, 2015 at 10:12 pm | Reply
I think you should have said explicitly which part of the proof fails for Z[sqrt(-5)]. Very nice articles, by the way.
A note on fractions | drcabana.org Says:
January 17, 2016 at 1:59 am | Reply
[…] q and q divides p(B^k), then m divides p(B^k). Now suppose m is a prime divisor of q. It is a deep and non-trivial fact that if a prime m divides a product p(B^k), then either m divides p or m […]
1 – Proving the Fundamental theorem of arithmetic Says:
July 18, 2016 at 11:26 pm | Reply
[…] justinhj […]
Christian Aebi Says:
September 1, 2016 at 4:09 pm | Reply
A small variation of Zermelo’s argument (that I find more “natural”) consists, like him in considering the smallest $n\in \mathbb{N}$, ($n>1$) admitting at least two decompositions $p_1 p_2\ldots p_i$ and $q_1 q_2\ldots q_j$, written both in ascending order, where $p_1$ is minimal among all possible decompositions of $n$. By minimality of $n$ we have $p_i \ne q_j$. By Euclidean division of $q_1$ by $p_1$ we get : $q_1=Qp_1+r$ with $0<r<p_1$. Multiplying both sides of the equality by $q_2\ldots q_j$ and subtracting the first term on the right gives (after a small transmutation):
$p_1\ldots p_i – p_1Qq_2\ldots q_j = r\cdot q_2\ldots q_j$
The right side being $r$.
- Christian Aebi Says:
  September 1, 2016 at 4:21 pm
  The end of my post seems to have been eaten up :
  The right side being $r$.
  PS. I also noticed that at a certain spot I should have written $p_s \ne q_t$ for all $s$ and $t$ (and not $p_i \ne q_j$).
Christian Aebi Says:
September 1, 2016 at 6:10 pm | Reply
Once again the end of the argument disappeared. The whole argument figures at the URL underneath (theorem 3), but in French. Sorry !
Question on Tim Gower’s Unique Factorization Proof [duplicate] – Mathematics – Forum Says:
March 4, 2023 at 10:26 pm | Reply
[…] See Tim Gower's blog post: How to discover a proof of the fundamental theorem of arithmetic.. […]
shay Says:
March 9, 2023 at 3:43 am | Reply
In the old linked post (with the more typical proof of Euclid’s lemma) https://www.dpmms.cam.ac.uk/~wtg10/FTA.html,

I’m not grasping this statement: “We are thus led to the following question: let p be a prime, let 0 < a < p and let h be the smallest integer such that p < ha. (It is not possible for p to equal ha since p is a prime and a clearly cannot equal 1 if p does not divide b.)"

Could someone rephrase the argument in parentheses?