18 ms·
Why isn’t the fundamental theorem of arithmetic obvious? (2011)
- cousin_it 10y agoIn math school we had a saying: "obvious means easy to prove". So the problem is about recognizing the difference between proofs and non-proofs. The hard but satisfying way to learn that difference is to start with axioms. Take some simple system of axioms that holds for Z, and try to prove the FTA from these axioms alone. Then check that the axioms aren't satisfied by Z[sqrt(-5)], or the even numbers, or some other ring where the FTA doesn't hold.
- thaumasiotes 10y agoEh. I read the commentary here and tried proving the fundamental theorem of arithmetic. Here goes: Suppose some integer k has two different prime factorizations -- it is the product of some set of n primes raised to nonnegative integer powers, and also of some other set of m primes raised to nonnegative integer powers. Call those sets p_n and p_m. Observe that there is no prime number which is assigned a nonzero exponent by p_n but not p_m, and there is no prime number which is assigned a nonzero exponent by p_m but not p_n. If p_n assigned a positive exponent to any prime c while p_m assigned c a zero exponent, then the product of p_n would be congruent to 0 (mod c), but the product of p_m would not, and therefore the two products would not equal the same number. (And symmetrically.) Therefore, p_m and p_n differ only in the nonzero exponents assigned to their various primes. Let g be the set of primes in p_m and p_n with the minimum exponent assigned by either p_m or p_n, let p_M be p_m with all exponents reduced by the exponent assigned by g, and let p_N be p_n with all exponents reduced by the exponent assigned by g. Observe that the exponent assigned to any prime is either 0 in each, or 0 in one of p_M or p_N and positive in the other. We can observe that, since p_m is not equal to p_n, one of p_M or p_N must assign a nonzero exponent to some prime. Let γ, μ, and ν be the integer products of g, p_M, and p_N. By hypothesis, γμ = γν, which means that μ = ν. But now we have two prime factorizations (p_M and p_N) of the same number (μ) for which one factorization assigns a positive exponent to some prime, and one factorization assigns an exponent of zero. By our earlier result we know that this is impossible. ---- I needed a lot of symbols, and if I were formally typing this up I'd need more, but it didn't seem like a very difficult proof -- I spent more time typing up this comment than working out the proof. Reading the piece, I see that it is specifically called out: > We’d be able to see instantly that 23 × 1759 ≠ 53 × 769 if we knew that a product of two non-multiples of 23 was always a non-multiple of 23. So I guess if you're comfortable with modular arithmetic, you can fairly consider this an obvious proof. It relies on another result about primes, but it's very common that one result makes another result easy, and a blanket disallowal of that approach leaves you saying that proving anything is as tricky and non-obvious as proving, proving, that 2+2=4.
- ColinWright 10y agoIf p_n assigned a positive exponent to any prime c while p_m assigned c a zero exponent, then the product of p_n would be congruent to 0 (mod c), but the product of p_m would not ... Why not? It seems at this point you are assuming something that is generally deduced as a consequence of the FTA. In particular, you have assumed that the product of the p_m is k (with appropriate exponents), and because c is in p_n we know that c|k, and hence we know that k=0 (mod c). So your claim here is false. It is actually assuming the FTA.
- evanpw 10y agoThis is correct. To be fair, though, the standard terminology is confusing: calling a number only divisible by 1 and itself a "prime" already assumes the FTA. In a more abstract setting, "p is prime" means that if p|ab, then p|a or p|b, and "irreducible" means only divisible by itself or a unit (in this case 1). The FTA corresponds to unique factorization into irreducibles, and the fact that irreducible and prime are the same thing is a consequence of unique factorization. (In an integral domain, every prime is irreducible; in a unique factorization domain, the converse is also true).
- deleted 10y ago[deleted]
- ColinWright 10y ago... the standard terminology is confusing: calling a number only divisible by 1 and itself a "prime" already assumes the FTA. Sort of, but not really. I'm not going to disagree with you, but make the following observation. People reading this article are likely to know about primes, and what you quote here is most likely the definition that they would be accustomed to. Introducing a new, technical term and then trying to describe the details of the difference would most likely derail the purpose, and abusing the terminology a little is perhaps justified, especially when it aligns with people's existing knowledge. But you are correct, and the reason we have these terms is exactly to avoid some of the "intuitively obvious" misconceptions.
- ingenter 10y agoWhy isn't 2+2==4 obvious? http://us.metamath.org/mpegif/mmset.html#trivia http://us.metamath.org/mpegif/mmset.html#trivia
- amelius 10y agoPerhaps you should read Principia Mathematica [1], which proves on page 379 that 1+1=2. [1] https://en.wikipedia.org/wiki/Principia_Mathematica https://en.wikipedia.org/wiki/Principia_Mathematica
- pavelrub 10y ago2+2=4 is obvious. The axiomatic proofs are mostly a meaningless and boring exercise that mathematicians invented when they wanted to axiomatize everything. They have nothing to do with whether something is obvious or not. It isn't as if it was possible to doubt that 2+2=4 before the invention of the Peano axioms.
- ingenter 10y agoI believe you're mistaken. There is value in axioms and axiomatic proofs: two different people will most definitively have a different notion of "obvious", and even have a different understanding of a mathematical problem. So a proof may be accepted by one person and rejected by another. Given a set of axioms and proofs it's possible to mechanically check a proof. It's not quite possible to reliably check proofs otherwise.
- hugh4 10y agoBut are people more likely to accept the axioms of Principia Mathematica (and the soundness of every logical step from page 1 to 300) than they are to accept the notion that 2 + 2 = 4 based on intuitive notions of what twoness, fourness and plusness are?
- CarolineW 10y agoOf course they are more likely to believe their intuitions. They also believe that it makes no difference whether or not you swap doors in the Monty Hall problem, and don't believe that with only 23 people the odds of a shared birthday are more than 50%. To some extent, there is the problem. People trust their intuitions, and their intuitions are often wrong. That's why for some things we need proper proofs.
- TopologyDough 10y ago"The fundamental theorem of arithmetic can be approximately interpreted 3 * 5 * 13 and 3 * 13 * 5" - this is false. The fundamental theorem of arithmetic "can be more approximately interpreted as " 195 has one prime factorization and it only includes one 3, one 5, and one 13 and no other primes. Once we find one prime factorization we want to prove that 195 does not have a prime factorization that includes another 11 or other prime.
- curiousgal 10y agoWhere did you read that?
- TopologyDough 10y agohttps://www.google.com/url?sa=t&source=web&rct=j&url=http://www.math.hawaii.edu/~lee/courses/fundamental.pdf&ved=0ahUKEwjrwfWIvbvNAhVZHGMKHe-1Aa4QFghbMA4&usg=AFQjCNE1fWsMtZ7DYjuIM-nL-dWQDshhXw&sig2=d4ys1EebbIuswQA9sc7bgQ https://www.google.com/url?sa=t&source=web&rct=j&url=http://... note that prime factorization is unique up to order. We aren't talking about order when we use the term uniqueness.
- ColinWright 10y ago... which is exactly what Gowers is saying in the second sentence.
- deleted 10y ago[deleted]
- ColinWright 10y agoIt doesn't say that. What it says is: 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 3x5x13 and 13x3x5 as the same, for instance. That's not the same thing at all.
- curiousgal 10y agoI've recently learned about Gödel numbering and I have to admit; it's my favourite application of this theorem. Sorry RSA.
- Smaug123 10y agoYou don't actually need FTA to perform Gödel numbering. ASCII will do just as well.
- curiousgal 10y agoYes. But Gödel originally used FTA, no?
- Smaug123 10y agoHe probably did. But for a programmer, ASCII is already something we're very familiar with, so why not use that?
- curiousgal 10y agoI didn't claim that FTA is the most practical way to perform Gödel numbering. I just said that it's my favorite application of it, in a general sense, not that I'd use it to do so. Preferences are subjective.
- kazinator 10y ago"Application" in mathematics usually means that something is used as a necessary component of a solution in another area. If Gödel numbering is an "application" of the FTA, that strongly suggests that you're saying that FTA somehow enables the possibility of Gödel numbering, or else that it is exploited somehow to endow that numbering with convenient properties (without loss of generality). Is that true?
- curiousgal 10y ago
- trengrj 10y agoI remember reading a proof to the fundamental theorem of arithmetic (every number is composed of a unique multiple of primes) in a number theory book and really enjoying it. I would disagree with Gowers and say it is obvious intuitively, but I'd still argue it is worth writing a proof for.
- Smaug123 10y agoIt really isn't obvious (I promise!), and Gowers's Answer 4 is "the real reason" for a mathematician. Alternatively viewed, it is not obvious that Euclidean domains are unique factorisation domains. (Though it is obvious that EDs are principal ideal domains, so the alternative view becomes "it is not obvious that PIDs are UFDs".)
- TopologyDough 10y agoThe link misinterprets FTA.
- rahimnathwani 10y agoAlthough it was ~30 years ago, I recall doing some school homework when we had just learned about prime numbers and factorisation. I remember trying to divide by random primes until I came across a factorisation. It wasn't at all obvious to me (at ~10 years old) that prime factorisations were unique or that they could be found using a simple repetitive algorithm. It seems obvious now, but only because I've never come across an integer with more than one factorisation. If there were an article on HN tomorrow with the headline 'Integer with more than one prime factorisation found' I wouldn't be able to resist clicking the link.
- AimHere 10y ago> If there were an article on HN tomorrow with the headline 'Integer with more than one prime factorisation found' I wouldn't be able to resist clicking the link. Curiously, I've only just found out that 48016416432886585186892071037001629018831524915070361 17449649760043615376581136847123881454516238486352419 62687300988949648670959062041377941995335910356581948 79838588416610716340382432762472099541373300228025778 94213135434471675634979394732216151334015571089605667 2861 has two distinct prime factorizations, thus providing a counterexample to Euclid's Fundamental Theorem of Arithmetic and showing that he made a mistake somewhere. Unfortunately the truly marvellous lists of factors are too small to fit in a Hacker News comment, so you'll have to rediscover the details yourself.
- PepeGomez 10y agoWouldn't multiple possible factorizations require numbers that both are and aren't divisible by certain numbers? If it's divisible by a number, the number must appear in its factorization and vice versa.
- ColinWright 10y agoWouldn't multiple possible factorizations require numbers that both are and aren't divisible by certain numbers? Yes. If it's divisible by a number, the number must appear in its factorization and vice versa. That is what the FTA says, so you are saying that the FTA is true, but that's just saying that you believe it. The article is trying to point out why once you know enough about how arithmetic works,it's no longer obvious. In particular, there are fairly natural rings that look very similar to the integers, but where this is not true. Taking the example in the linked article, it's true if we extend the integers by sqrt(-1), but it's not true if we extend the integers by sqrt(-5). In that ring we have: 2 x 3 = (1 + sqrt(-5))x(1 - sqrt(-5)) So (1 + sqrt(-5)) appears in one factorisation of 6, but not in another. So in this case, factorisations are not unique.
- deleted 10y ago[deleted]
- bluecalm 10y agoObvious is different than easy to prove. The concepts of multiplication, division, prime number and "divisible by" are much older than formal proofs and arbitrary sets of axioms. Let's say I only now what multiplication is and that AxB = BxA and that prime number can't be written as AxB unless A or B are 1. Now it's obvious that there are factorings of a number: you just divide it by smallest possible prime divider until you reach 1, that process obviously terminates every time and produces a finite factoring. Now let's assume that our number A has two factorings F1 and F2. Let's sort them from the smallest to the biggest divider. Is it possible that F1 and F2 are different at the first position? It isn't as that would mean the same number has different smallest prime divider. We therefore divide our number by the prime divider at that first position and continue the process proving that dividers at all the positions must be the same or that F1 F2 are factorings of a different number. It is in fact obvious to someone who understands multiplication. As to some points from the article: >>it is obvious that 23\times 1759 is not the same number as 53\times 769. It is, we sort them from the smallest to bigger prime in the factorization. If they were the same number that would mean the same number's smallest prime diviser is 23 and 53 at the same time. You may want to argue that it's not obvious that to be divisible by a prime number it must appear in a factorization - here I just assume you understand it's obvious for anyone who knows what multiplication is and that the fact that it's not obvious to your system with your axioms is your problem altogether. >>If it’s so obvious that every number has a unique factorization, then why is the corresponding statement false in a similar context? It's not a similar context, at least for non-mathematician. You are introducing some weird objects in the form of a + b*sqrt(-5). I may not even understand the concept of a complex number but I still can understand FTA. Btw, for that FTA isn't obvious because there is no order for those objects, it's not clear what is bigger or smaller than something else and which position given object is in if we sort them from the smallest. I get it: FTA is hard to prove in your nice formal system with your nifty arbitrary chosen axioms and formal deduction rules. It's bloody obvious to the caveman who can do multiplication by putting stones in a rectangle though.
- jackmaney 10y agoA nice discussion, but a bit of a nitpick: in Z[sqrt(-5)], 2, 3, 1+sqrt(-5), and 1-sqrt(-5) are actually irreducible, not prime. In an integral domain D, a nonzero element x is called irreducible if x is not a unit and whenever x = ab (for a, b in D), then one of a or b is a unit. On the other hand, a nonunit element x in D is called prime if for all a, b in D, if x divides ab then x divides a or x divides b (by "x divides ab", I mean that there's some element--call it y--in D such that xy = ab). In Z (or any unique factorization domain[1]), these concepts coincide. In Z[sqrt(-5)], however, there are irreducible elements that are not prime. In particular, 2 is irreducible in Z[sqrt(-5)], but it isn't prime, since 2 divides (1+sqrt(-5))*(1-sqrt(-5)), but 2 divides neither 1+sqrt(-5) nor 1-sqrt(-5). [1]: https://en.wikipedia.org/wiki/Unique_factorization_domain https://en.wikipedia.org/wiki/Unique_factorization_domain
- n4r9 10y agoThis is brought up at the top of the comments section, along with Gowers' response and a neat comment from someone called Fabian: >It seems it is the thoughtless combination of the definitions of “prime” and “irreducible” that makes the theorem appear obvious.
- hackuser 10y agoThis is from 2011.
- deleted 10y ago[deleted]
- cousin_it 10y agoSome more theorems that seem obvious but require non-trivial proofs: https://en.wikipedia.org/wiki/Intermediate_value_theorem https://en.wikipedia.org/wiki/Intermediate_value_theorem https://en.wikipedia.org/wiki/Jordan_curve_theorem https://en.wikipedia.org/wiki/Jordan_curve_theorem https://en.wikipedia.org/wiki/Isoperimetric_inequality https://en.wikipedia.org/wiki/Isoperimetric_inequality https://en.wikipedia.org/wiki/Hairy_ball_theorem https://en.wikipedia.org/wiki/Hairy_ball_theorem https://en.wikipedia.org/wiki/Schr%C3%B6der%E2%80%93Bernstein_theorem https://en.wikipedia.org/wiki/Schr%C3%B6der%E2%80%93Bernstei...
- illivah 10y agoI know I'm wrong, but it feels like tis' in the definition of what a prime factor is, a prime factor being the fundamental indivisible integers. If so, considering that multiples of the same numbers are always the same, and all numbers that are prime are indivisible, the only way the conjecture could be false is if there were indivisible numbers that aren't prime. Definition inconsistency. That's why I'm not a mathematician.
- ColinWright 10y agoProblem is, we only ever mess about with small numbers. Take some absolutely humungous number, N, and find, somehow, that it's a times b. Suppose someone else asserts that it's c times d. These numbers are enormous, absolutely enormous, so the question is: if a, b, c, and d are all prime, is it really obvious that these two ways of writing N have to be the same? Edit: As pointed out elsewhere (and in the sibling to this comment) there are systems where "prime" and "irreducible" are not the same thing. In the integers they are, and that's sort-of why the FTA is true, but in other places they aren't, which is why the FTA is not obvious.
- dazmax 10y agoIt could also be false if there were two different pairs of prime numbers with the same product. See Answer 4 in the article.
- illivah 10y agoAh I love it when my error is so simple that there isn't any question in my mind I missed something.
- owenjonesuk 10y agoActually, you're pretty much spot on. The word you want is "irreducible", rather than "indivisible". In general rings there are irreducible elements and prime elements, and they have different definitions. You're looking for a unique factorisation into irreducibles. https://en.wikipedia.org/wiki/Irreducible_element https://en.wikipedia.org/wiki/Irreducible_element https://en.wikipedia.org/wiki/Prime_element https://en.wikipedia.org/wiki/Prime_element
- pflats 10y agoI'm going to be a little bit contrarian and disagree. I totally see where the author is coming from, but it comes across of mathematical self-aggrandizement. I especially disagree with his interpretation of the layman's experience. They're not assuming the proof or begging the question; they have a secondary unrealized assumption that is not at all their fault. The fundamental theorem of arithmetic is "obvious" because we grow up learning a system where if p|ab then p|a or p|b. As mathematicians, we know that Euclid's lemma is a requirement for a unique factoring domain, and we understand that the choice of set can affect whether the lemma is true. For a non-mathematician, this is an inherent part of their conception of numbers, factoring, and their definition of the word prime. Put yourself in the position of talking to someone who thinks prime factorization is "obvious". Where will things go wrong in their explanation? In answer 2: they have a completely deterministic way to prime factor, and it relies on Euclid's lemma. So you ask them: "Well we know 6 is divisible by 2. What if we break it into 2 numbers that aren't divisible by 2?" "Well then this wouldn't work. But that's not possible." "But what if it was?" "But that's not how numbers work." "But what if I took each of those numbers and replaced them with two numbers and that I'm going to call one big number. And when I multiply those together I'm going to multiply the first number of each pair together, then multiply the second number of each pair together. Then I'll multiply the result of that second multiplication with -5, and add that final answer with the product of the first pair I did earlier." "uh" "If I do that, then do you believe that I could get two factors of 6 where neither pair of numbers is completely divisible by 2? Try (1,1) and (1,-1) and you'll see that it works: 1 x 1 = 1, 1 x -1 = -1. That -1 x -5 = 5, plus the original 1 gives me 6. See! It's not obvious." "Yeah, uh, you didn't tell me I could make a new type of number and multiplication up on the spot." "No no no, it's all mathematically sound. You see, those second numbers are just the coefficients of the square root of negative 5." "Okay, so is there any rule I've learned that I can trust?" "So I bet you think it's obvious that when you add two numbers, you can always get an answer..." We are essentially telling kids that (American) football is a game where two groups of people line up, block, run formations and routes, give the ball to someone, and try to get it into the end zone for points. Then, when it's your turn to go on offense, you drop back, throw a pass to your undefended wide receiver, and act amazed that the other team didn't even consider that you might throw the ball simply because you didn't forbid it. The fundamental theorem of arithmetic was proven around 1,800 years before sqrt(-5) was even conceived of. Over two millennia before Ring Theory. Those proofs were correct for the systems in which they were written. They might even be obvious within that system. That that they are not generally true does not change things.
- deleted 10y ago[deleted]
- mcguire 10y agoThat's not my question. My question is, why is it the fundamental theorem of arithmetic?
- twic 10y agoYeah! I do arithmetic most days, and i very rarely have to prime factorise anything!
- nilkn 10y agoI know I'm going up against a brilliant mathematician and Fields medalist here, but I find this article to be unenlightening. It seems that Gowers has glossed over something about the integers that's built incredibly deeply into our intuition about them when he talks about Z[sqrt(-5)]: > 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}. He skipped over the fact that the positive integers are well-ordered by < (and in fact < also respects the arithmetic operations on the positive integers as well). I just can't take the comparison seriously without this being explicitly discussed, because the ordering of the integers is incredibly fundamental to human intuition about them.
- GFK_of_xmaspast 10y agoHere's a stumper then: why do Z[sqrt(-1)] and Z[sqrt(-3)] have unique factorization but Z[sqrt(-5)] doesn't?
- nilkn 10y agoDid you mean to write Z[sqrt(-2)] instead of Z[sqrt(-3)]?
- GFK_of_xmaspast 10y agohttps://en.wikipedia.org/wiki/Eisenstein_integer https://en.wikipedia.org/wiki/Eisenstein_integer
- nilkn 10y agoBut Z[sqrt(-3)] is not the ring of Eisenstein integers. Regardless, the fact that Z[sqrt(-n)] is a UFD for n = 1,2 but not for n >= 3 is indeed quite counter-intuitive. But Gowers isn't asking whether it's intuitive for Z[sqrt(-n)]. He's asking about the positive integers, and the positive integers have a very special well-ordering which respects the arithmetic operations and for which humans have quite a powerful intuition. I maintain that Z[sqrt(-n)] is more different from Z than Gowers is letting on and that if you actually look at all the differences, rather doing the opposite and trying to make it seem similar to Z, you'll quickly realize why people feel that the FTA is not very bizarre for Z but it is for Z[sqrt(-n)].
- evanpw 10y agoEvery one of the bad arguments that Gowers points out have been made in this thread full of smart people, even after everyone read the article. I think that's pretty good evidence that the theorem really isn't obvious.
- ColinWright 10y agoWhat's the bet most of them have at best skimmed the article, and that many haven't even bothered to read further than the first few paragraphs, if at all. Edit: typo
- cousin_it 10y agoI've kinda stopped believing that high intelligence always leads to high quality discussions. Every HN thread about math or physics has many misguided comments, coming from people who are probably very smart in their own fields. I've seen that on LessWrong too, really smart math/CS people talking about biology can get demolished by a second year biology student. Noticing my own cluelessness about a topic is a very subtle skill, it took me years to learn and I'm probably not there yet. Sometimes I even feel that math/CS education has damaged me in some ways, made me too arrogant, though obviously it gave me a huge advantage in other ways.
- semi-extrinsic 10y agohttps://xkcd.com/793/ https://xkcd.com/793/
- delazeur 10y ago> I've seen that on LessWrong too, really smart math/CS people talking about biology can get demolished by a second year biology student. IMO, LessWrong and other communities based around critical thinking tend to either foster a sense of intellectual arrogance or attract people who already have that quality. > Sometimes I even feel that math/CS education has damaged me in some ways, made me too arrogant, though obviously it gave me a huge advantage in other way. A lot of education in science and engineering is based around teaching people to walk up to a problem they are completely unfamiliar with and make a reasonable attempt at solving it. That is an extremely useful skill in some cases, but very dangerous in others.
- snake_plissken 10y agoI agree 50%. But, it becomes pretty obvious once you realize the significance of prime numbers, their applications and the scarcity of them.
- NobleSir 10y agoMy favorite proofs of these basic number theory facts are in Apostols, Intro to Analytic Number Theory. At best the FTA using the proof there is only slightly less than obvious (of course obviousness probably varies widely based on mathematical background / maturity).
- Chinjut 10y agoSure, to a mathematician, these things become old hat, but note that Apostols spends several pages developing properties of the GCD that aren't generally considered "obvious"; in particular, he argues for Theorem 1.2 (that any two integers a and b have a common divisor of the form ax + by, which is in turn therefore divisible by all their other common divisors) by tracing out the steps to recursively compute this combination-as-GCD (i.e., the Euclidean algorithm), recast as an inductive proof. I don't think the layperson would find this obvious at all (in the way they might have claimed FTA to be obvious), or even be aware of this fact, though it plays a key role in building up to the eventual proof of the FTA.
- zwischenzug 10y agoI'm surprised Wittgenstein hasn't been mentioned here. He thought and wrote extensively about the foundation of mathematics. In fact, the write-ups of a series of his lectures features discussions between him and Turing (and other luminaries) about what maths is about (and W tends to come over stronger on the subject): https://www.amazon.co.uk/Wittgensteins-Lectures-Foundations-Mathematics-Cambridge/dp/0226904261 https://www.amazon.co.uk/Wittgensteins-Lectures-Foundations-... It's great fun to read.
- Someone 10y agoLet me try to explain with an example outside of mathematics: All swans are white. For centuries (possibly millennia, as Juvenal thought it, too), that was obvious (in western Europe) to anyone studying nature. Then, Willem de Vlamingh returns from a journey to Australia with some dead black swans. Now, there are various options. Some of them are: - You can drop your claim that all swans are white. - You state these aren’t swans because they aren’t white. Both have merit, but even if you choose the latter, it is hard to keep claiming that it is obvious that all swans are white. This is somewhat similar. Smart men have studied numbers for centuries, and have thought hard about what it means to be a number. They came up with a set of properties and laws that they thought was necessary and sufficient for a set of objects to behave like numbers. The fundamental theorem of arithmetic was not in that list, as it was thought one could derive it from simpler laws, or, possibly, nobody even thought of doing that, as they thought it to be obvious (I do not know enough of the history of mathematics to know which is true) Suddenly, somebody comes up with a set of objects that abides by those laws, but for that set, the fundamental theorem of arithmetic does _not_ hold. Now, you can claim that set of objects isn’t a set of numbers, but you can no longer claim that the fundamental theorem of arithmetic is obvious.
- psyklic 10y agoGowers argues that even without considering generalizations of the reals, it is not "obvious". He argues that if the Theorem were "obvious", we should quickly be able to say that 23 x 1759 != 53 x 769, without multiplying them out.
- Someone 10y agoBut that's a weak argument. By that token, checking whether two numbers add up to a third or whether two numbers are equal or even whether two numbers have the same number of digits aren't obvious, if you make the numbers large enough. "Can be answered quickly" is not a good indicator of "is obvious".
- contravariant 10y ago
- ball_of_lint 10y agoIt actually becomes much easier to understand if you approach it from the other direction. Some assumptions - A prime is only evenly divisible by itself and one. - One is not a prime. - A composite number is generated by multiplying two or more primes. - No number of primes can be multiplied together to make another prime. That would mean that the so called prime generated is composite. Now, say we have a number n with two different prime factorizations, f1 and f2, where f1 includes a certain prime p, and f2 does not, and where n is evenly divisible by p, and n/p = m. Now, if f1 and f2 are both prime factorizations of n, then consider what happens when we do this: f1 = p * m = f2 m = f2 / p f2 does not contain p, and we cannot construct a prime p from other primes or composites. This means that f2 cannot be evenly divisible by p, as that would require it to have a prime factor of p which it does not. Therefore f2 cannot be another prime factorization of n. That may not be perfectly rigorous, but I'm certain the gist of it is true.
- justinhj 10y agoI'm no mathematician but this makes sense to me. I'll be interestsd in seeing how the article follow up proves the same.
- CarolineW 10y agoSomething I learned a long time ago is this: if someone claims to have a proof, trying following the same proof in a different case where the conclusion is actually false, and see where their "proof" fails. So let's try applying your reasoning to the example given in the linked article. There it shows that in the integers extended by sqrt(-5) we have 2x3=(1-sqrt(5))x(1+sqrt(5)). So using your specific reasoning: Let's take n=6 f1 : 2 x 3 f2 : (1-sqrt(5)) x (1+sqrt(5)) p : 2 m : 3 You now say: f2 does not contain p, ... Correct. ... and we cannot construct a prime p from other primes or composites. True. This means that f2 cannot be evenly divisible by p, as that would require it to have a prime factor of p which it does not. But f2 is evenly divisible by p, despite not including p in the list of primes being multiplied together to give n. So your line of logic fails at this point. This is actually assuming (something equivalent to) the FTA. The example shows a case where f2 is evenly divisible by p, so your deduction here is wrong. It is subtle.
- vladsotirov 10y agoThis blog post illustrates well the infuriating tendency of academics to teach by calling people stupid. The substance of his answers are: 1. " If you think it’s obvious, then you’re probably assuming what you need to prove" i.e. "If you think this, you're wrong." 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" i.e. "If you think doing it this way works, it doesn't." 3. "Look, it just bloody well isn’t obvious, OK?" i.e. "If you get frustrated that I keep telling you you're wrong, that's your fault for being wrong." 4. "If it’s so obvious that every number has a unique factorization, then why is the corresponding statement false in a similar context?" i.e. "I won't tell you what you did wrong, but instead I'll show you why your answer can't possibly be right." It is unconscionable that he does not identify the actual fact people erroneously use without justification when thinking the fundamental theorem is obvious. FYI, that fact is "If a number n can be written as the product of a fixed list of (not necessarily distinct) primes p_1, p_2, ..., p_n, then any prime p dividing n appears on this list." (there is a minority of mathematicians who refer to this fact as the fundamental theorem of arithmetic, not unique prime factorization; the obvious argument is going from the fact to unique prime factorization, proving the fact is the unobvious argument)
- pjdorrell 10y agoMy own attempt to deal with this issue (2013): http://thinkinghard.com/blog/UniqueFactorisation.html http://thinkinghard.com/blog/UniqueFactorisation.html
- playerqq 10y agoI haven't looked at any proofs for the FTA. Could somebody point out if I made any mistakes on the one I've arrived at? [1] Proof by induction that if a positive integer has a prime factorization, then it is unique. We're inducting over Z_N, where Z_N is the set of all positive integers with at least one known prime factorization using exactly N number of primes. Call this factorization Pn = p_1 * p_2 * ... p_n For every case, split into proof by cases and contradiction: suppose there is an element Z in set Z_N had another factorization Fn. - If Fn has the same number of factors as Pn, divide both sides by p_i. Since Fn / p_i must be an integer, Fn must contain p_i, or else one of its factors f_i actually isn't prime by Euclid's Lemma. - If Fn has k more factors than Pn, then divide Pn by (f_1 * f_2 * ... * f_n). Then (f_n+1 * ... * f_n+k) = X for some composite integer X > 1. Thus Fn = X * (f_1 * f_2 * ... * f_n) = (p_1 * p_2 * ... * p_n) = Pn. Since (p_1 * p_2 * ... * p_n)/Z must be an integer, Z must divide into one of the factors p_i by Euclid's lemma, which is impossible since they are prime by definition. - Similar argument to above if Pn has more factors. [2] Proof by contradiction: Every positive integer Y greater than one has a prime factorization. Suppose not. We know Y = Y * 1. So Y must be composite in order for it to not have a prime factorization. Hence, we know that Y = a * b, (a, b > 1). At least one of the two must be composite or else Y has a prime factorization, so let's say (a) is composite. Then a = c * d (c, d > 1). Then at least one of the two factors must be non prime or else we've found the prime factorization for Y. Repeat ad infinitum to show that if Y does not have a prime factorization, then it must be the product of an infinite number of composite factors, with every factor great than 1. Hence contradiction. So every positive integer greater than 1 has a prime factorization, and it must be unique.
- Someone 10y ago"If Fn has the same number of factors as Pn, divide both sides by p_i. Since Fn / p_i must be an integer, Fn must contain p_i, or else one of its factors f_i actually isn't prime by Euclid's Lemma." You would have to prove that first. https://en.m.wikipedia.org/wiki/Euclid%27s_lemma https://en.m.wikipedia.org/wiki/Euclid%27s_lemma: "This property is the key[4] in the proof of the fundamental theorem of arithmetic [4] In general, to show that a domain is a unique factorization domain, it suffices to prove Euclid's lemma and ACCP." (https://en.m.wikipedia.org/wiki/Ascending_chain_condition_on_principal_ideals https://en.m.wikipedia.org/wiki/Ascending_chain_condition_on... looks more intimidating than Euclid's lemma to me, but may be easier to prove.)
- lacker 10y agoI think a lot of people consider uniqueness of prime factorization to be obvious just because it's stated as true so frequently. If you want to convince someone it's not obvious, I would ask them a simpler, weaker question: Can you find four different prime numbers, a b c d, so that ab = cd? If not, why not? You may not cite unique-prime-factorization. They will find themselves really wanting to cite unique prime factorization, and unable to prove it otherwise, which will convince people that it's not obvious.