Hacker News Reader

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 positive integers has a least element.

The reason your proof didn't seem difficult is because you glossed over the difficult parts and your proof isn't a proof.

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

Nope, it's actually a restatement of a lemma traditionally used to prove the Fundamental Theorem of Arithmetic, and quite a nice one too in my opinion. (It's "obviously" true in the sense that any exception feels like it'd violate basic behaviour we'd expect from modulo arithmetic on primes, and with a bit of head-scratching it even seems to be possible to prove that.)

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.

If it's lacking a correct proof it needs to be proven.

To be fair, you were not rigorous enough to call that a proof and I think you know that. So there's really no point in arguing semantics here, it's just giving maths a bad look.

> To be fair, you were not rigorous enough to call that a proof and I think you know that.

On the contrary. Referring to a well-known result without proving it in situ is very common. For example, I also assume without proving that if two integers a, b have the property that ka = kb, then a is equal to b. You don't see anyone complaining about that.

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

But Gowers' point is that FTA relies on a deep fact that is non trivial (as pointed out and proven elsewhere on this thread, the correctness of Euclidean division: https://en.wikipedia.org/wiki/Euclidean_division#Proof). You can sidestep this by using other lemmas in arithmetic, but at some point everything is resting on this one deep fact.

Also, it's not like proving that 2+2=4, which follows trivially from Peano's axioms and the definitions of 2, 4, and +. If something is nontrivial to prove, it's usually because there is something deeper going on beneath. In this case, the fact that Euclidean division works for the integers, but not for other number systems (e.g., Z[sqrt(-5)]), is what makes it deep and interesting.

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

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

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

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<b<p, and trivially nb = 0 mod p. So there is some smallest b', 0<b'<p for which nb' = 0 mod p. We can also see nb'r = 0 mod p for all integers r. Find the smallest r for which b'r >= 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.

> 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, and hence we know that k=0 (mod c). So your claim here is false.

I don't see any problem there? I say that k = 0 (mod c) because c is in p_n, and k ≠ 0 (mod c) because c is not in p_m. That's a contradiction, which is what I wanted to show. The remaining possibility is that p_n and p_m contain the same prime factors in different quantities, and the rest of the proof reduces that case to this same contradiction.

EDIT -- ColinWright has quoted text which I edited out of this comment; his quote is accurate.

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

> But you should say that you are relying on this.

I do say that. It's right there at the bottom of my comment.

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

Others have taken potshots at this, and I'll join them. Look at the examples (in the article) of Z[sqrt(-5)]:

    6 = (2, 0) x (3, 0)   =>   p_n = {(2,0), (3,0)}
    6 = (1, 1) x (1, -1)  =>   p_m = {(1,1), (1,-1)}

So we have non-uniqueness of the factorization for this case. So we follow the logic of the excerpt above -- c=(2,0) is assigned a zero exponent in the second factorization, and indeed, p_n is congruent to 0 (mod c). Also, p_m is congruent to 0 (mod c). So where do we get the contradiction?

The proof of this statement outlined below by makomk does establish this fairly well for the integers, and the argument cannot apply to Z[sqrt(-5)], but only because we can't define an ordering on Z[sqrt(-5)]. Z[i] _is_ a unique factorization domain (despite the lack of ordering), so fundamentally this proof is lacking in its ability to establish unique factorization for a particular ring. Though it does work for the integers, because of the well-ordered property, which is very non-obvious from your proof (and the whole article is about obviousness, not correctness, so this is relevant)

Euclid proved it in ancient Greece and you can look up his proof online. It's pretty succinct, though his proofs can sometimes be hard to follow as the Greeks had a different conception of number to the modern one.