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

101–110 of 210 posts

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

#101

Post by clux »

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…

Damn that Fermat margin.

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

#102

Post by [deleted] »

ColinWright wrote: post #45
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 longe…

[deleted]

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

#103

Post by [deleted] »

evanpw wrote: post #34
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…

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

[deleted]

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

#104

Post by pavelrub »

thaumasiotes wrote: post #98
pavelrub wrote: post #78

Earlier quoted context omitted.

I’ve already told you what to do if the term “pure black” causes problems. The color represented by #600000 on my monitor is always darker than the color represented by #FF0000, regardless of the existence of any theory of color. If you claim that some formal theory of color convinced you of that, then it would mean that a different theory of color could conceivably convince you otherwise. But this is clearly impossi…

But none of this is true. #600000 on your monitor might be lighter than #FF0000 on your monitor if they're compared at different times, or if part of your monitor happens to be in the shade. Or if I have a weird viewing angle to your monitor. If you want to argue about what #600000 and #FF0000 should look like, you're back to a rigorous theory of color.

No, because I can be very specific about the condition of my monitor, without reference to any theory of color (I can just say: in the exact conditions my monitor is in at this moment, or in the conditions of a darkened room, where no external light source can make #600000 lighter than #FF0000) . I can hypothetically also show you my monitor in person, in any conditions I choose. In fact I don’t even have to talk about my monitor or those specific colors. We can talk about the color of space as seen from the ISS on the dark side of earth, versus the color of the sun when visible from the ISS. Or the color of my room at night vs the color of a candle flame. There are millions of examples we can think of without talking at all about any theory of color. I mean - it is a matter of fact that words such as “darkness” and “lightness” existed before the invention of rigorous representations of color, and that the numerical definition of those words was designed on purpose to coincide with their existing meaning, and not with some new arbitrary property of color. So I’m not even sure what you are arguing against.

But the whole argument about colors is really unnecessary, I only used it because I thought it would be simpler to understand, but I might have been wrong. If you don’t think that it supports my argument about 2+2=4, feel free to ignore it and address the argument itself.

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

#105

Post by [deleted] »

yequalsx wrote: post #40
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…

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…

[deleted]

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

#107

Post by mcguire »

pavelrub wrote: post #92
czinck wrote: post #71

Earlier quoted context omitted.

There's a lot of historical context you're missing if you think axiomatic proofs are meaningless. Around the late 1800s, a few contradictory proofs started popping up because people weren't being rigorous enough (the example I know involved proofs about pointwise vs uniformly continuous functions just being referred to as "continuous"). Then a few paradoxes were discovered (like Russel's paradox, the set of all sets…

I think I wasn't clear enough. I never meant that axiomatic proofs in general are meaningless, only that axiomatic proofs of trivial arithmetic facts (1+1=2, 2+2=4...) are meaningless.

You have two choices here:

1. You assume "trivial arithmetic facts" as axioms.

Result: You have an infinite number of axioms. (Whee!) The likelihood that you have snuck in non-trivial assumptions is pretty high, unless you are very strict about how you define "trivial" (which is probably as much work as just proving the trivial facts), and in that case, there's a high probability that some of your trivial facts are false.

2. You demonstrate that you can prove "trivial facts" in your system and you do so when needed by more complex proofs. The proofs of trivial facts are not necessarily trivial.

In neither case is your handling of "trivial facts" meaningless.

Quod erat demonstrandom.

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

#108

Post by schoen »

PepeGomez wrote: post #99
Chinjut wrote: post #94

Earlier quoted context omitted.

Who says "if it's divisible by a number, the number must appear in its factorization"? Why is that true? For example, 24 is divisible by 6, though 24 has the prime factorization 2 * 2 * 2 * 3, with no 6 to be found. "Right, but all the prime factors of 6 appear in the prime factorization of 24. If X is divisible by the prime p, then there is a unique prime factorization of X, which must include a factor of p", you ma…

No other prime is divisible by 3 than 3 itself and so on. And you can't ever get a number divisible by 3 by multiplying numbers that are not divisible by 3. (3n-1) * m mod 3 and (3n-2) * m mod 3 cycle predictably and never become zero unless m mod 3 = 0. The same principle should hold for every number.

The mod-cycling-predictably property also holds for composite numbers, while I think the "can't get a number divisible by 3 by multiplying numbers that are not divisible by 3" part relies on the fundamental theorem of arithmetic! (Otherwise, how do we know that you can't get a number divisible by 3 by multiplying numbers that are not divisible by 3, yet the same doesn't hold for 4? I think that's the fundmental theorem of arithmetic back again in another guise.)

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

#110

Post by nilkn »

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

Post reply on HN