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

Oh, don't worry; the "you" in "I think you're..." was generic (for anyone who claims complete and utter obviousness of unique prime factorization without ability to explicate the reasoning behind it or even grasp that reasoning might be required) and not targeted at YOU per se; I'm not accusing you of lacking mathematical sophistication. It was clear from your other comments that you have significant background in mathematics.

I'm just accusing you of being misguided when claiming that humans are able to access uniqueness of prime factorization as obvious because of special inbuilt integers-with-That is:

Sure, all you need is that, in arithmetic modulo a prime, nonzero values are closed under multiplication.

But this fact is not obvious! The only reason to believe this is via, implicitly or explicitly, the reasoning that tells us how to compute GCDs as linear combinations (what I have referred to as "the Euclidean algorithm" for shorthand, though I do not mean to fixate on any particular presentation of such reasoning).

Here is makomk's argument: "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."

That is good, that is fine, that is the sort of argument one needs. But I would not consider that to be at all "obvious" in the way laypeople often claim UPF to be. It takes some insight or work to see the possibility of that argument! There's no reason to consider that sort of argument as deep-in-our-bones obvious, implicit to laypeople by basic intuition about integers-with-(FWIW, makomk's argument is also closely related to the following natural algorithm for computing the gcd of A and B: starting with an initial guess x which is any combination of A and B, keep replacing x with any nonzero value among either A % x or B % x (up to negation, if you like), till eventually one cannot continue reducing x in this way; at all times, x is a combination of A and B, and one must stop by finding such a combination that divides both A and B (and is therefore their GCD). This isn't quite the Euclidean algorithm as usually presented, but serves just as well as an algorithm computing GCDS-as-combinations recursively, and makomk's argument essentially follows the structure of computing the GCD of m and p in this way)

But nevermind the full generality of GCD computation. That may be a distraction from the point I intended to make. (I phrased things in terms of this because it was the easiest wording, but that's not quite what I'm concerned about). Even just the special case of this reasoning used by makomk is not something "obvious". I do not believe the layperson who claims UPF to be obvious has an argument like makomk's latent in their head. I think they are just making unjustified leaps. I think they are, as I said, just presuming UPF obvious because they've never seen it fail and have heard it discussed so many times and so on, to the point that they can't even conceptualize that any further reasoning could be called for.

As for "using the properties I've mentioned", presumably in reference to the integers being a well-ordered ring: sure, being a unique factorization domain follows from being a well-ordered commutative ring where the ordering interfaces with the ring structure in the expected ways... because the ONLY well-ordered ring is the integers, and the integers are a UFD. But I still don't think the average person, when looking at uniqueness of factorization as "obvious", is accessing the reasoning that goes into this.

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

As for the remark at the end: you're right, it may be difficult to un-obfuscate phrased in that form, but had you phrased it "Make a table of two columns. Take the very top-most, left-most entry to be n, take every entry in the right column to be 1 plus the value to its left, and take every further entry in the left column to be the product of all previous entries in the right column. I claim the value three cells below the initial n has three prime factors (and similarly the value below that has four prime factors, etc.)", and I couldn't see why that would be the case, then, yes, this would give some real pause as to whether I could truly claim sound understanding (to the point of considering it obvious) of the reason for the infinitude of primes.

And if, analogously, the obstacle to someone seeing "the smallest positive value of the form 98X - 60Y is 2" is merely inability to factorize 98 or 60, well, that doesn't mean much. But I don't think that's the obstacle for most; I don't think people would do much better were it phrased "What is the smallest value of the form 2 * 7^2 * X - 2 * 3 * 5 * Y? (BTW, 2, 3, 5, and 7 are all prime)". And I do think, while not definitive in itself, the fact that this sort of thing is not obvious at all to people suggests we shouldn't presume sound reasoning behind uniqueness of prime factorization/Euclid's lemma/etc. is implicitly obvious either. When people claim it to be obvious, it's not because they have a dim view of the correct reasoning, seen through a glass, darkly. It's just because they're making complete logical leaps.

This 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)