Why isn’t the fundamental theorem of arithmetic obvious?

The fundamental theorem of arithmetic states that every positive integer can be factorized in one way as a product of prime numbers. This statement has to be appropriately interpreted: we count the factorizations 3\times 5\times 13 and 13\times 3\times 5 as the same, for instance. Note that it is essential not to count 1 as a prime, or else we could stick a product of 1s on to the end of any factorization to get a different one: 3\times 5\times 13=3\times 5\times 13\times 1\times 1\times 1. But doesn’t that mean that 1 itself cannot be written as a product of primes? No — we define the “empty product” (what you get when you take a bunch of … no numbers at all and multiply them together) to be 1. That is a sensible convention because we would like multiplying a product of numbers by the empty product not to make any change to the result.

That’s enough about what the fundamental theorem of arithmetic says. In this post I want to discuss the question of why it is a theorem at all. Isn’t it more like an observation? After all, given any number, we can simply work out its prime factorization.

Answer 1. If you think it’s obvious, then you’re probably assuming what you need to prove.

If you say, “we can simply work out its prime factorization,” you are already assuming that that factorization is unique. Otherwise, you would have had to say, “we can simply work out a prime factorization for it”. Of course, if you say it that way, it suddenly doesn’t seem quite as obvious that there’s only one. If you’re trying to argue that it’s obvious and you ever utter the phrase, “the prime factorization,” then you are begging the question, since implicit in those words is the assertion that there is only one prime factorization.

Answer 2. Just because you’ve got a completely deterministic method for working out a prime factorization, that doesn’t mean what you work out is the only prime factorization.

The following method is probably how you factorize a number: you divide it by 2 as many times as you can (which may be no times at all), then by 3, then by 5, and so on, keeping track of what you’ve done. For example, if your starting number is 575, then you can’t divide it by 2 or 3, but you can divide it by 5 to get 115, and then by 5 again to get 23, and then … well, you’ll probably know that 23 is prime, but you could also argue that since 5^2 is greater than 23 and you’ve checked 2 and 3, then it must be prime.

But just because that method always gives the same answer (the method in the abstract being to keep dividing by the smallest prime that goes into the number you see in front of you), that doesn’t mean that there might not be some other method that gives a different answer. For example, what if you looked for the largest prime that went into your number? You’re probably thinking that you’ll just get the same list of primes, but written backwards. But how do you know this? Obviously that’s what you’ll get if there’s only one way of writing the number as a product of primes, but that’s what we’re trying to prove. If there’s another way of writing it as a product of primes, then perhaps the largest prime in the other way of doing things is larger than the largest prime that results from the usual method.

Answer 3. Look, it just bloody well isn’t obvious, OK?

Sorry, I lost it for a moment there. But if you persist in thinking that it’s obvious, then perhaps you can tell me why it is obvious that 23\times 1759 is not the same number as 53\times 769. I’ll save you a little time by revealing that all of 23, 53, 769 and 1759 are prime. I will not accept as an answer that if you calculate those two products you get different results. That to me is an admission that it wasn’t obvious that the answers would be different. If it was obvious, then why bother to calculate them?

By the way, I’ll grant you that sometimes it’s obvious that two products of primes are different. For example, if 2 is involved in one product and not the other, then the first product is even and the second is odd. However, even that second assertion depends on the (simple) result that a product of odd numbers is odd. We’d be able to see instantly that 23\times 1759\ne 53\times 769 if we knew that a product of two non-multiples of 23 was always a non-multiple of 23. But is there an easy way of showing that? We can work out the multiplication table mod 23, but that’s a bit tedious. Alternatively, we can use some theory from the course — but unless you’re finding the course so easy that that theory (a proof derived from Euclid’s algorithm) is utterly obvious, then I don’t think you can call it obvious that 23\times 1759\ne 53\times 769.

Here’s another pair of products of primes for your delectation and delight: 47\times 863 and 73\times 557. Are they obviously different? It’s not clear which is bigger — they’re both a little over 40,000. What about the last digit? Damn, 1 in both cases. OK, let’s go for the second last digit, which is a bit of a cheat but still. In the first case we get the last digit of 4\times 3+7\times 6+2, which is 6. In the second case we get the last digit of 7\times 7+3\times 5+2, which is again 6. So we’ve got two numbers that are a little bit above 40,000 that both end 61. As it happens 47\times 863=40561 and 73\times 557=40661.

If you wanted a quicker demonstration that those two numbers are different, you could work out what they are mod 3, which is a lot easier than working them out completely. But that’s not going to work in general. For instance, it doesn’t work for the first example, where the smallest modulus for which they differ is 7. If I took two pairs of absolutely huge numbers (with millions of digits), I could get them to agree in almost all their digits and differ by a multiple of, say, 1000! And even if such small-modulus tests can be used, it isn’t obvious in advance that they will work if it isn’t obvious in advance that the products are different.

Answer 4. If it’s so obvious that every number has a unique factorization, then why is the corresponding statement false in a similar context?

Consider the collection of all numbers of the form a+b\sqrt{-5} where a and b are integers. (You might prefer to write these numbers as a+ib\sqrt{5}, but I prefer \sqrt{-5} for reasons that I don’t want to go into here, but might mention in a future post.)

These numbers have various properties in common with the integers: you can add them and multiply them, there are identities for both addition and multiplication, and every number has an additive inverse. And as with integers, if you divide one by another, you don’t always get a third, so the notion of divisibility makes sense too. That means that we could if we wanted try to define a notion of a “prime” number of the form a+b\sqrt{-5}.

Just before I try to do that, let’s quickly decide what we mean by a prime when we allow negative numbers. Presumably we’re going to want, say, -5 to be a prime, but what definition will lead to that? The small technical obstacle we face is that if we allow negative primes like that, then for a somewhat silly reason factorizations won’t be unique: for instance, 15=3\times 5=(-3)\times(-5). The usual approach to this is to divide numbers into three kinds: prime numbers, composite numbers, and units. A unit is a number that has a multiplicative inverse, so in \mathbb{Z} the units are 1 and -1. A prime is a number that cannot be written in the form ab unless exactly one of a and b is a unit. (I said “exactly” one because I didn’t want accidentally to define units themselves to be primes.) And now we can express the fundamental theorem of arithmetic in \mathbb{Z} by saying that every number has exactly one factorization into primes, except that we count two factorizations as the same if the only difference (apart from the order) is that the primes in one factorization are multiplied by units to give the primes in the other factorization. For example, we count 3\times 5 and (-5)\times(-3) as the same, since we can reorder the second factorization as (-3)\times(-5) and then multiply both primes by the unit -1 to get 3\times 5, which gives us the first factorization.

In short, what we’re saying is that if two products of primes don’t obviously give the same number, then they give different numbers.

Right, back to numbers of the form a+b\sqrt{-5}. Let’s check that 2 is a prime in this ring. (A ring in this context is, roughly speaking, an algebraic structure with addition and multiplication with all the usual axioms apart from the existence of multiplicative inverses. You can think of it as something a bit like \mathbb{Z}. However, the actual definition is a bit more general, as you can find out from the relevant Wikipedia article. Hmm, I’ve just looked at that article and I don’t like it at all: the list of examples is woefully inadequate. The important examples are eventually mentioned, but not in the list of basic examples, so you don’t get a good idea that they are the important ones.) First of all, 2 isn’t a unit, since 1/2 is not of the form a+b\sqrt{-5}. The modulus of a+b\sqrt{-5} is \sqrt{a^2+5b^2}, so if b\ne 0, then the modulus of a+b\sqrt{-5} is bigger than 2. It follows that the only way of writing 2 as a product of non-units would have to be to write it as a product of non-unit integers, which we can’t. So 2 is prime.

A similar check can be run for 3. So 2 and 3 are primes. It’s also possible to show that 1+\sqrt{-5} and 1-\sqrt{-5} are primes. But 2\times 3=(1+\sqrt{-5})(1-\sqrt{-5}), so 6 has a non-unique factorization into primes. (It’s also easy to see that you can’t multiply 2 or 3 by a unit to get one of 1\pm\sqrt{-5}.)

Why is this a problem for people who hold that the fundamental theorem of arithmetic is obvious? It’s because they have to explain what it is about \mathbb{Z} that is relevantly different from the ring of numbers of the form a+b\sqrt{-5}, which is denoted \mathbb{Z}(\sqrt{-5}). Why can’t we just translate any proof that works for \mathbb{Z} into a proof that works for \mathbb{Z}(\sqrt{-5})?

Here’s an example of how you can use \mathbb{Z}(\sqrt{-5}) to defeat somebody who claims that the result is obvious in \mathbb{Z}. Let’s take the argument that you can just work the factorization out by repeatedly dividing by the smallest prime that goes into your number. Well, you can do that in \mathbb{Z}(\sqrt{-5}) as well. Take 6, for instance. The smallest prime (in the sense of having smallest modulus) that goes into 6 is 2. Dividing by 2 we get 3, which is prime. So we’re done. So there can’t be another factorization. Except that there is another factorization. So the argument just isn’t an argument.

In a future post I’ll discuss the proof of the fundamental theorem of arithmetic. But this post is just to try to convince you (if you needed convincing, which you may not have) that the result is worth going to some effort to prove.

About these ads

31 Responses to “Why isn’t the fundamental theorem of arithmetic obvious?”

  1. Joel Says:

    Very nice!
    I note that the definition of “prime” you give looks to be the definition corresponding to the notion of “irreducible” in a more general ring. However, I understand that this corresponds most closely to the definition of prime that students will be used to, and that the two notions coincide in this setting. Moreover, not everyone likes to define prime elements in rings anyway, preferring to work with prime ideals instead.

    • gowers Says:

      Yes, it’s worth being clear about this, even if it won’t affect things for Cambridge IA students. So if you don’t already know the difference between prime elements and irreducible elements, here it is. An element of a ring is called irreducible if it is not a product of more than one non-unit, and it’s called prime if whenever it divides a product ab it divides at least one of a and b. The two definitions coincide in \mathbb{Z}, but this is non-obvious (in that it depends on Bézout’s theorem). Thus, when I defined “primes” in \mathbb{Z}(\sqrt{-5}), I was being a bit informal: the standard terminology for what I was defining is actually the irreducible elements.

      The point about the non-obviousness of the fundamental theorem of arithmetic still stands, however: any proof of unique factorization in \mathbb{Z} (into irreducibles, which are the same as primes) must be an argument that does not generalize to \mathbb{Z}(\sqrt{-5}).

    • Fabian Says:

      It seems it is the thoughtless combination of the definitions of “prime” and “irreducible” that makes the theorem appear obvious.

  2. Gaurav Tiwari Says:

    1 is empty product of primes.

    I was always confused with “empty product” and zero times summation.
    a^0=1 means \displaystyle{\underbrace{a \times a \times \ldots a}_{\mathrm{0 \ times}}} and I thought here the result should be nothing or zero (both differ in sense). I am not sure about how empty product is defined? My professor told me that this rule is valid for positive natural numbers only.

    • Veky Says:

      I think the most useful thing for you to contemplate is _why_ exactly you think that the answer should be zero. And I think it is because of the unfortunate terminology “0 times” below the brace. Of course, 0 times a is 0. But why? Because of distributivity: b=b+0, so a*b=a*(b+0)=a*b+a*0, so a*0 should be the identity for addition, that is, 0.

      Distributivity for powers looks different: a^(b+c)=a^b*a^c. So b=b+0 means a^b=a^(b+0)=a^b*a^0, and a^0 should be the identity for multiplication, that is, 1.

      Negative way to look at this is: if a^0 is 0 (and a different from 0), then a^(0+1)=a^1=a is not equal to a^0*a^1=0*a=0. And we would like to have distributivity.

    • John Baez Says:

      I spend a lot of time explaining to students why the empty product – the product of nothing at all – is 1. I’m too lazy to type all this stuff in, but here’s one way to see that it’s at least somewhat plausible.

      2^0 = ?
      2^1 = 2
      2^2 = 4
      2^3 = 8

      What’s the pattern here? Each number is twice as big as the one before it. So what should the first number be? It should be 1, since that will continue the pattern. Having it be 0 would ruin the pattern.

      If you keep the pattern going, 2^0 will work just like the other powers of 2 and you life will be happy. If you destroy the pattern by decreeing that 2^0 = 0, this power of 2 will act different from all the rest, and your life will be forever miserable (until you quit doing math, but please don’t do that).

      One important thing to realize is that in math, we get to make up the rules. It’s not true that God decreed 2^0 = 1 and it’s our job as humble servants to memorize this rule. We make up the rules. But we try very hard to choose rules that give simple patterns. ‘Exceptions’ are not nice.

    • El-Andalussi Says:

      “I was always confused with “empty product” and zero times summation.”

      We should always think about a number as a cardinality of a power set. This way we can understand better why 2^0=1. From the fact that cardinality of an empty set is 0, we can say that the power of this set is 1 since it contains only one element, the empty set. And, then, for all integer n, n^0=1 …

  3. Mugizi Robert Rwebangira Says:

    Minor typo in the paragraph after Answer 3:

    “23, 52, 769 and 1759 are prime” should be “23,53,769 and 1759 are prime”

    Oops — thanks!

  4. Dakota Says:

    Another good example of where unique factorization fails is the even numbers. Irreducibles are of the form 2k where k is odd and 36 = 18*2 = 6*6.

    • gowers Says:

      For some reason I find this example less convincing. At one level that’s for the simple-minded reason that I can see that “really” the factorization of 36 is 2\times 2\times 3\times 3. But I don’t know what that means in the abstract. The most obvious difference between the even numbers and \mathbb{Z}(\sqrt{5}) is that there aren’t any units in the even numbers, but it’s not clear what the existence of units contributes to the perception that the fundamental theorem of arithmetic is obvious.

      Maybe the reason we have different expectations of the even numbers, and are therefore not terribly surprised that unique factorization fails, is that we lose all sense of multiplication as repeated addition: the fact that 6=2+2+2 ought to be telling us that 6 is 2 times something, but it isn’t. But this is not saying much more than that the even numbers don’t contain a multiplicative identity.

    • Noah Snyder Says:

      This issue (where there’s an obvious “right factorization” outside the allowed set) also comes up with non-integrally closed subrings of integrally closed rings.

      My personal favorite example of a ring without prime factorization is C[x,y,z,w]/(xy-zw).

    • gowers Says:

      I certainly see the appeal of that …

    • Sune Kristian Jakobsen Says:

      Inspired by the comment above, that the even numbers is not a good example because there its “real” factorization is in Z and is unique, I wanted to ask:

      Is there a similar ring for Z[\sqrt{-5}]? That is, a ring that contains Z[\sqrt{-5}] in which factorization is unique.

      Unfortunately, there are trivial answers to that, e.g. \mathbb{C}. So can anyone think of the question I should be asking? Or a better answer?

    • Anonymous Says:

      Let $a=\sqrt{-5}$, $b=\sqrt{5}$, $i=\sqrt{-1}$

    • Anonymous Says:

      Let $a=\sqrt{-5}$, $b=\sqrt{5}$, and $i=\sqrt{-1}$, then consider the ring

      $$ R = Z[a,(a+i)/2] $$

      Then $R$ contains $Z[a]$ and it’s a UFD, for instance:

      $$ 6 = (1+i) * (1-i) * (1+a-b-i)/2 * (1-a-b+i)/2 $$

      where

      $$ (1+i) * (1-i) = 2 $$

      $$ (1+a-b-i)/2 * (1-a-b+i)/2 = 3$$

      $$ (1+i) * (1+a-b-i)/2 = 1 + a $$

      $$ (1-i) * (1-a-b+i)/2 = 1 – a $$

      In other words, 2, 3, 1+a and 1-a decompose further in this ring.

      NOTE: the ring $R$ has infinitely many units! For instance: $i$ and $(a+i)/2$ generate the group of units.

    • Noah Snyder Says:

      If I remember correctly, every element in a ring of integers of a number field k factors uniquely as a product of primes in the ring of integers of the Hilbert class field of k. This is one possible answer to Sune’s question. My recollection is that every number field sits inside a number field where the ring of integers has unique factorization, but that’s harder to prove and I might be misremembering.

    • obryant Says:

      I take the lesson from these examples that if factorization isn’t unique, then you need to go further. That’s “obvious” for the even integers. For Q(\sqrt{-5}), the correct notion of “further” is to think of ideals rather than numbers. This motivates ideals, too.

    • David Speyer Says:

      Noah: I think your final sentence is wrong. There are certainly examples of infinite class field towers — where K doesn’t have unique factorization, so you stick it in the class field K’ where all ideals of K become principal, then K’ also doesn’t have unique factorization so you go up to the class field K” and so forth. I thought I remembered that, for such a K, there is no number field L with class number 1 containing it. I could be wrong though.

    • Cam McLeman Says:

      David: Yup, that’s right. A field admits a finite extension with class number 1 if and only if its class field tower terminates.

  5. Noah Snyder Says:

    Fantastic post. I basically gave up on teaching unique factorization related topics at a summer program I worked at, because even if I could eventually convince students that they couldn’t prove unique factorization, they still felt it was too obvious to be interesting. It’s still very weird to me that people are so attached to it being obvious. I hadn’t thought of trying arguments in the style of your Answer 3, so I’m curious whether that works. My experience has been that Answer 4 is psychologically ineffective.

  6. Nyaya Says:

    I think the problem with a basic result like the fundamental theorem of arithmetic is that since it is true for the only mathematical object people have truly handled since kindargarten, there is nothing in their experience that would suggest that it could be otherwise — that the fact that the decomposition is unique is strange. This makes the result obvious. I think your answer 4 really shows the fly the fly-bottle. (On a slightly dissimilar note, I have met people who don’t find the infinitude of primes strange. However, showing them a way of generating consecutive numbers of any length that doesn’t contain a prime does muddy the waters a bit. )

  7. sjt Says:

    The post says \mathbb{Z}(\sqrt{5}) where I’d expect to see \mathbb{Z}[\sqrt{5}]. Not sure if I’m just missing the point.

  8. David Speyer Says:

    When presenting arguments like your Answer 3, if I have had time to prepare in advance, I sometimes like to sneak in “How would you see that 1357 x 4183 is not the same as 1081 x 5251?”

  9. Proving the fundamental theorem of arithmetic « Gowers's Weblog Says:

    [...] Gowers's Weblog Mathematics related discussions « Why isn’t the fundamental theorem of arithmetic obvious? [...]

  10. John Baez Says:

    When I get back to UC Riverside I’ll probably teach number theory again someday, and these blog posts will really come in handy.

    Convincing people that obvious-sounding things aren’t really obvious, but are still true, is a psychologically difficult chore. “It isn’t obvious, but it’s true, and if you follow this incredibly complicated line of reasoning you’ll see why” – that doesn’t sell, because it seems you wind up just where you started (knowing that something is true) after having done a lot of extra work. There are not many situations in life where it’s worthwhile going to elaborate pains to verify something you’re already sure is true.

    This sort of thing appeals to pathologically careful people, and these people may be born mathematicians. There are other people who can learn the appeal of being pathologically careful, as a kind of mental discipline or game, and maybe these people are the target audience for a course like this. There are other people who can understand the idea of being pathologically careful, but find it a tiresome chore. And there are others who don’t get it all. For the latter two types, I try to make sure my course has a lot of other fun stuff in it!

  11. Daniel Sargent Says:

    I’m glad you wrote this. I intend to read it carefully when I have more then just my phone to do so. But I was so excited that I perhaps have something to add. Consider that if two prime factorizations did exist for a number, say p1*p2=n and p3*p4=n, then we have the following ratio between primes: p3:p1=p2:p4.
    Proof: a:b=c:d, then
    ac:ab=c:d, then
    ac:bc=ac:ad, so
    bc=ad.
    Just one possibility of non unique prime factorization, but with the conclusion accepted, indicating the nonexistence of primes with the ratios.

  12. Fundamental theorem of arithmetic » Zyymat: Mathematics Says:

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

  13. CatSynth » The Fundamental Theorem of Arithmetic » CatSynth Says:

    [...] for our everyday arithmetic to hold. A good article on why the theorem is not obvious can be found here. It also has implications beyond the natural numbers. If we extend the canonical representation to [...]

  14. dieting when your pregnant Says:

    I do not even know how I ended up here, but I thought this post
    was good. I do not know who you are but certainly you are going to
    a famous blogger if you aren’t already ;) Cheers!

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


Follow

Get every new post delivered to your Inbox.

Join 1,562 other followers

%d bloggers like this: