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

41–50 of 210 posts

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

#41

Post by AimHere »

rahimnathwani wrote: post #28
trengrj wrote: post #9

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

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

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

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

#43

Post by vinchuco »

AimHere wrote: post #41
rahimnathwani wrote: post #28

Earlier quoted context omitted.

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

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

Your comment has destroyed the browsing experience on mobile :)

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

#44

Post by AimHere »

vinchuco wrote: post #43
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…

Your comment has destroyed the browsing experience on mobile :)

Hah. Apologies for that! I thought the downvotes were because it was a lame joke, not that I was destroying the site!

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

#45

Post by ColinWright »

PepeGomez wrote: post #42

Wouldn'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.

    Wouldn'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.

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

#46

Post by ColinWright »

AimHere wrote: post #41
rahimnathwani wrote: post #28

Earlier quoted context omitted.

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

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

Please edit this to restore the formatting to something usable.

Edit: Thank you.

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

#47

Post by pathsjs »

PepeGomez wrote: post #42

Wouldn'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.

> If it's divisible by a number, the number must appear in its factorization and vice versa.

By writing "its" factorization, you are already assuming that there is only one

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

#48

Post by wlesieutre »

vinchuco wrote: post #43
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…

Your comment has destroyed the browsing experience on mobile :)

Also on desktop. Can we get some max-width and overflow:scroll in here?

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

#49

Post by makomk »

ColinWright wrote: post #27
thaumasiotes wrote: post #26

Earlier quoted context omitted.

Eh. 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 expo…

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…

Brief outline of an argument: suppose nm = 0 mod p (p prime) and m != 0 mod p. We can write this as n(ap+b) = 0 mod p for some integers a, 0= p. If b' != 1, then since p is prime b'r != p and we get a smaller b'' := b'r-p for which n*b'' = 0 mod p, a contradiction. Therefore b' = 1 and n = 0 mod p.

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

#50

Post by jackmaney »

A 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

Post reply on HN