Hacker News Reader

Comment by ColinWright | Hacker News Reader

    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.

View on HN

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.

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.

Reply on news.ycombinator.com