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

*Let be a prime number and let and be positive integers. Then if it follows that or .*

as this

*Let be a prime number and let and be positive integers such that mod . Then either mod or mod .*

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.

*Let be a prime number and let be a positive integer such that mod . Then there exists such that mod .*

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.

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

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.

*Let be a prime number and let be a positive integer that is not a multiple of . Show that there is an integer and another integer such that .*

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 .

**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 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.

November 19, 2011 at 12:22 am |

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)

November 19, 2011 at 5:24 am |

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.

November 19, 2011 at 8:26 am |

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.

November 19, 2011 at 9:11 am

I’ll have to think about that …

November 19, 2011 at 9:50 am |

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.

November 21, 2011 at 7:57 pm |

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

November 22, 2011 at 2:28 am |

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.

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.

November 22, 2011 at 6:03 am |

[…] 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. […]

November 22, 2011 at 11:25 pm |

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 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 by left multiplication by . That is, in my mental image of this part of the proof, we start off with this congruence, and it is modified to . 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.

November 23, 2011 at 2:21 pm |

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.

November 23, 2011 at 2:23 pm |

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.

November 24, 2011 at 2:19 pm |

[…] 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. […]

November 24, 2011 at 8:34 pm |

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.

November 25, 2011 at 6:14 pm |

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.

November 26, 2011 at 1:11 pm |

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).

November 26, 2011 at 3:06 pm

I didn’t exactly forget the congruence sign — it’s more that I was “thinking mod “, 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?

December 26, 2011 at 4:26 am |

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.

April 26, 2012 at 7:41 am |

[…] 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 […]

October 3, 2012 at 9:35 pm |

[…] Gower 写了两篇关于此定理的博客文章: Why isn’t the fundamental theorem of arithmetic obvious? 和 Proving the fundamental theorem of arithmetic. […]

January 16, 2015 at 12:58 pm |

Why is a group homomorphism in the proof of Lemma 1? I don’t get . Do I miss something?

January 17, 2015 at 4:19 pm

The group in question is under addition, not multiplication.

January 16, 2015 at 2:53 pm |

Dear Prof. Gowers,

In the proof of lemma 1, the image of is indeed a subgroup of as you’ve shown in the second paragraph right after slogan 12. But I don’t think it is because “ is a homomorphism”.

April 8, 2015 at 10:12 pm |

I think you should have said explicitly which part of the proof fails for Z[sqrt(-5)]. Very nice articles, by the way.

January 17, 2016 at 1:59 am |

[…] 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 […]

July 18, 2016 at 11:26 pm |

[…] justinhj […]

September 1, 2016 at 4:09 pm |

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$.

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$).

September 1, 2016 at 6:10 pm |

Once again the end of the argument disappeared. The whole argument figures at the URL underneath (theorem 3), but in French. Sorry !

March 4, 2023 at 10:26 pm |

[…] See Tim Gower's blog post: How to discover a proof of the fundamental theorem of arithmetic.. […]

March 9, 2023 at 3:43 am |

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?