«
»

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.

This entry was posted on November 13, 2011 at 11:33 am 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.

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

  1. Joel Says:
    November 13, 2011 at 12:48 pm | Reply

    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:
      November 13, 2011 at 2:32 pm

      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:
      November 13, 2011 at 4:11 pm

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

  2. Gaurav Tiwari Says:
    November 13, 2011 at 2:02 pm | Reply

    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:
      November 15, 2011 at 9:14 am

      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:
      November 19, 2011 at 2:28 am

      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:
      November 24, 2011 at 3:18 pm

      “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:
    November 13, 2011 at 2:31 pm | Reply

    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:
    November 13, 2011 at 4:20 pm | Reply

    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:
      November 13, 2011 at 6:03 pm

      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:
      November 13, 2011 at 6:21 pm

      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:
      November 13, 2011 at 7:06 pm

      I certainly see the appeal of that …

    • Sune Kristian Jakobsen Says:
      November 13, 2011 at 7:59 pm

      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:
      November 14, 2011 at 1:20 am

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

    • Anonymous Says:
      November 14, 2011 at 1:30 am

      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:
      November 15, 2011 at 1:30 am

      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:
      November 17, 2011 at 3:12 am

      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:
      November 17, 2011 at 5:44 pm

      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:
      February 26, 2012 at 5:05 pm

      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:
    November 13, 2011 at 5:26 pm | Reply

    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:
    November 13, 2011 at 8:49 pm | Reply

    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:
    November 14, 2011 at 5:02 pm | Reply

    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:
    November 17, 2011 at 5:48 pm | Reply

    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:
    November 18, 2011 at 11:47 pm | Reply

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

  10. John Baez Says:
    November 19, 2011 at 2:42 am | Reply

    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:
    July 29, 2012 at 12:47 am | Reply

    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:
    October 3, 2012 at 9:31 pm | Reply

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

  13. CatSynth » The Fundamental Theorem of Arithmetic » CatSynth Says:
    December 28, 2012 at 11:13 pm | Reply

    […] 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:
    February 13, 2013 at 5:03 pm | Reply

    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!

  15. A note on fractions | drcabana.org Says:
    January 17, 2016 at 2:20 am | Reply

    […] 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 divides B^k (or both). […]

  16. 5 – Why isn’t the fundamental theorem of arithmetic obvious? Says:
    February 6, 2016 at 9:21 pm | Reply

    […] From: https://gowers.wordpress.com/2011/11/13/why-isnt-the-fundamental-theorem-of-arithmetic-obvious/ […]

  17. Chris Hills Says:
    March 4, 2016 at 5:13 pm | Reply

    Very good post. Yes, unique factorisation is not obvious, it has to be proved. But isn’t the proof fairly simple? I don’t see the need for the complicated induction proof at https://gowers.wordpress.com/2011/11/18/proving-the-fundamental-theorem-of-arithmetic/.

    Let’s suppose that there are numbers that have more than one factorisation. Then there must be a smallest one. Let’s say it’s C. Then C = A = B, where A = a_1*a_2* … *a_N, and B = b_1*b_2*…*b_N, and all the a’s and all the b’s are prime.

    Every a is different from every b. If that were not the case then there would be a common factor, which we could divide by, to get a smaller C with more than one factorisation. But C is the smallest one.

    A is divisible by a_1. Therefore B must be divisible by a_1. Therefore a_1 must divide one of the b’s, b_i (say). Then b_i is not prime. But all the b’s are prime. This is a contradiction. So our supposition that there are numbers that have more than one factorisation is incorrect. QED.

    • gowers Says:
      March 5, 2016 at 8:32 am

      The bit of your argument that makes a non-obvious jump is the statement “Therefore a_1 must divide one of the b’s, b_i (say).”

  18. Why isn't the orbit-stabilizer theorem obvious? - MathHub Says:
    March 19, 2016 at 9:06 pm | Reply

    […] title of this post paraphrases the title of a great blog post by Timothy Gowers, where he argues that those who think that the fundamental theorem of arithmetic […]

  19. calcilater Says:
    June 22, 2016 at 2:09 pm | Reply

    I suppose there are two different things in this article that are both called modulus. One is for modular reduction the other seems to be something like a norm or metric. Could you elaborate a bit on the latter? Especially the part “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.” is intriguing. Is there only one possible way to define a metric for this ring? Or is this just the canonical way to do it? What’s going on here? 🙂
    I looked at https://en.wikipedia.org/wiki/Modulus_(algebraic_number_theory) but like many other wikipedia articles on math it was not very helpful.

  20. krusta80 Says:
    June 22, 2016 at 2:21 pm | Reply

    Perhaps this is too simplified, but it has always been my understanding that prime numbers (and therefore number theory) only apply to positive integers. After all, they certainly cannot apply to fractions or irrational numbers.

    So why use imaginary numbers in your argument at all?

    • calcilater Says:
      June 22, 2016 at 2:49 pm

      If you look at fields (which the rational and real numbers are) there are indeed no “primes” or numbers such that a | bc => a | b or a | c.
      For other rings however this makes perfect sense. Consider for example the ring of polynomials. What can you divide x + 3 by?

    • krusta80 Says:
      June 22, 2016 at 2:53 pm

      I would think any fractional power of (x + 3) for starters. But are we assuming that x is an integer?

  21. Anonymous Says:
    June 23, 2016 at 12:54 am | Reply

    There might be a simple proof by contradiction along these lines:

    1) a is prime means there exists no number between 2 and a-1 that divides it
    2) there exists a prime factorization of every integer (algo exists for calculating it)
    3) let a prime factorization be pi0 * pi1 * … pin
    let a different prime factorization be pj0 * pj1 … pjm
    pi0 * … pin = pj0 * … pjm
    pi0 must divide pj0 * … pjm
    thus pi0 must divide some pj, since it itself cannot be written as a product of 2 or more primes
    this is a contradiction, so there cannot be a different pj0 … pjm

    • gowers Says:
      June 23, 2016 at 7:51 am

      The bit that’s not obvious there (though it’s true) is the step where you deduce that pi0 must divide some pj.

  22. Doug Spoonwood Says:
    June 25, 2016 at 10:45 pm | Reply

    There exists more to it. The way multiplication gets symbolized there exists the suggestion that it qualifies as a binary operation. Thus, when we write something like 2 x 3 x 5, notation suggests we’ve represented a product of the number 2 and, a product of 3 and 5. Or it suggests we’ve represented a product of the product of 2 and 3, and 5. Which of those interpretations holds depends on the author. Now, you might feel tempted to say that the association of multiplication makes that irrelevant, but remember the theorem says that there exists a product of prime numbers *only* (the above two statements consist of a product of a number and *a product*, or a product of *a product* and a number). And thus if multiplication consisted of a binary operation, it would immediately fail in a case like the factorization of 30, since [2 x (3 x 5)] = [2 x 15] which is a product of a prime number and a composite number, while [(2 x 3) x 5] = (6 x 5) which is the product of a composite number and a prime number.

    When talking about the theorem Gowers here wrote that the factorization of 36 is 2 x 2 x 3 x 3. But the composite number 36 by that notation looks like a product of a number and a composite number (2 x 18), a product of a composite number and a composite number (4 x 9), or a product of a composite number and a prime number (12 x 3). A notation like x(2, 2, 3, 3) or (2, 2, 3, 3)x doesn’t get used all that often when talking about the Fundamental Theorem of Arithmetic. And thus, it’s not so obvious, because authors don’t use appropriate notation to theorem all that often when talking about it or make it clear that the theorem implies that for any composite number, there exists of a k-ary product of prime numbers only, where k is some natural number.

  23. #9: Seriousness of the Fundamental Theorems of Mathematics | math - update Says:
    December 9, 2016 at 1:02 am | Reply

    […] Source: Gower´s blog […]

  24. #9: Pure Awesomeness of the Fundamental Theorems of Mathematics | math - update Says:
    December 9, 2016 at 4:02 am | Reply

    […] Source: Gower´s blog […]

  25. Anonymous Says:
    December 10, 2019 at 2:41 pm | Reply

    What? It’s very obvious…

    If n has two prime factorizations, then we can divide both by some prime divisor p of n. This corresponds to simply erasing a prime factor from each (p|ab implies p|a or p|b), giving us two prime factorizations of p/n. Repeat until we reach 1, and you’ll see that the two prime factorizations were in fact the same.

  26. Number Theory (Get Started Here) Says:
    January 4, 2020 at 6:01 am | Reply

    […] the next subsection, several lemmas are studied. The penultimate part of this chapter is about the Fundamental Theorem of Arithmetic. Within it, the author characterizes primes, provides proof of the Fundamental Theorem, and then […]

  27. Under what operation prime numbers form a group? – Math Solution Says:
    March 28, 2022 at 9:49 pm | Reply

    […] theorem of arithmetic (existence and uniqueness of prime factorizations for integers) is taken for granted too often as an obvious fact. It isn’t as obvious as you might think; there are number rings which do not have prime […]

Leave a comment