Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Why isn’t the fundamental theorem of arithmetic obvious? (2011)

gowers.wordpress.com

Post reply on HN
Print view View original

61–70 of 210 posts

Re: Why isn’t the fundamental theorem of arithmetic obvious? (2011)

#61

Post by cousin_it »

thaumasiotes wrote: post #56
yequalsx wrote: post #40

Earlier quoted context omitted.

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. Herein is the problem. This observation of yours needs to be proven and is in fact the whole point of the proof of the Fundamental Theorem of Arithmetic. That's the hard part. You'll also need to use the fact that every nonempty set of the…

That sentence is followed by a proof. You can say the proof is wrong, but you're missing the point to say "it needs to be proven".

Why can't the product of two primes A and B be congruent to 0 modulo some other prime C? It's trivial that A * B can't be equal to C, but not as easy to show that it can't be 2 * C, say.

Re: Why isn’t the fundamental theorem of arithmetic obvious? (2011)

#62

Post by AimHere »

CarolineW wrote: post #57
AimHere wrote: post #41

Earlier quoted context omitted.

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

I would rather trust the proof of the Fundamental Theorem of Arithmetic than trust the bald and unsupported assertion by someone I don't know and haven't heard of. Sorry. :-(

Oh, that's fine.

I don't want anyone to trust me, I just wanted to get the OP to go to the trouble of checking up on me, since he or she is willing to go at least partways in that direction :)

Re: Why isn’t the fundamental theorem of arithmetic obvious? (2011)

#63

Post by ColinWright »

thaumasiotes wrote: post #59
ColinWright wrote: post #27

Earlier quoted context omitted.

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 ... 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 k…

> Why not? It seems at this point you are assuming something that is generally deduced as a consequence of the FTA. According to the OP, this result does not rely on the FTA -- he claims to derive it from the Euclidean Algorithm. makomk does the derivation in a sibling comment. > 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, an…

    >> Why not? It seems at this point
    >> you are assuming something that is
    >> generally deduced as a consequence
    >> of the FTA.

    > According to the OP, this result
    > does not rely on the FTA -- he
    > claims to derive it from the
    > Euclidean Algorithm.
Yes.

    > I can't do that, so I'm taking
    > his word for it, but that doesn't
    > make the proof circular.
But you should say that you are relying on this. As it is you are simply making an unsupported assertion, and so your proof is incomplete.

See other comments in this sub-thread for more explanations.

Re: Why isn’t the fundamental theorem of arithmetic obvious? (2011)

#64

Post by thaumasiotes »

yequalsx wrote: post #60
thaumasiotes wrote: post #56

Earlier quoted context omitted.

That sentence is followed by a proof. You can say the proof is wrong, but you're missing the point to say "it needs to be proven".

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. This is basically just a restatement of the Fundamental Theorem of Arithmetic. See Gower's Answer 3 in his post.

No, it's not, and I specifically quoted the part of Gower's Answer 3 that mentions it in my original comment.

If you think this is a restatement of the fundamental theorem of arithmetic, maybe you think of the FTA as obvious after all. ;p

Re: Why isn’t the fundamental theorem of arithmetic obvious? (2011)

#65

Post by thaumasiotes »

cousin_it wrote: post #61
thaumasiotes wrote: post #56

Earlier quoted context omitted.

That sentence is followed by a proof. You can say the proof is wrong, but you're missing the point to say "it needs to be proven".

Why can't the product of two primes A and B be congruent to 0 modulo some other prime C? It's trivial that A * B can't be equal to C, but not as easy to show that it can't be 2 * C, say.

This was answered in the same comment tree before you posted the question: https://news.ycombinator.com/item?id=11953790

Re: Why isn’t the fundamental theorem of arithmetic obvious? (2011)

#67

Post by cousin_it »

thaumasiotes wrote: post #65
cousin_it wrote: post #61

Earlier quoted context omitted.

Why can't the product of two primes A and B be congruent to 0 modulo some other prime C? It's trivial that A * B can't be equal to C, but not as easy to show that it can't be 2 * C, say.

This was answered in the same comment tree before you posted the question: https://news.ycombinator.com/item?id=11953790

Yes, I know the proof. The point is that your original proof sketch didn't acknowledge the need for that lemma.

Re: Why isn’t the fundamental theorem of arithmetic obvious? (2011)

#69

Post by [deleted] »

jessriedel wrote: post #37
thaumasiotes wrote: post #33

Earlier quoted context omitted.

> This is like saying that we need a rigorous theory of color in order to be convinced that black is darker than red. You do, if you want to be right. The fact that you can get people to agree with you doesn't make you right, and red is frequently darker than black by some pretty normal definitions of "darker". Red and black are differentiated by the shape of their reflective spectrum, not the amplitude.

You guys are basically arguing over Moore's here-is-one-hand problem. https://en.wikipedia.org/wiki/Here_is_one_hand pavelrub's point is that you sometimes have less reason to believe the axioms of your formalization than their derived consequences. We have better reason to believe the intuitive idea that 2+2=4 than we do any putative axioms of arithmetic. If we derived that 2+2=5 from some particular axioms of arith…

[deleted]

Re: Why isn’t the fundamental theorem of arithmetic obvious? (2011)

#70

Post by thaumasiotes »

pavelrub wrote: post #58
ingenter wrote: post #55

Earlier quoted context omitted.

There is no pure black in the real world.

There is theoretical pure black in any modern representation of color. If the term confuses you, you can replaces it with #000000. If the black vs red comparison still confuses you, you can replace it with #600000 vs #FF0000. You might also want to address my actual argument, instead of irrelevant technicalities.

How are you getting a "theoretical pure black" without having a rigorous theory of color? If you're just going to call some things black and some things red, you'll find that a lot of things that people call black are lighter than a lot of other things that people call red.
Post reply on HN