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 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.)
Therefore, p_m and p_n differ only in the nonzero exponents assigned to their various primes. Let g be the set of primes in p_m and p_n with the minimum exponent assigned by either p_m or p_n, let p_M be p_m with all exponents reduced by the exponent assigned by g, and let p_N be p_n with all exponents reduced by the exponent assigned by g. Observe that the exponent assigned to any prime is either 0 in each, or 0 in one of p_M or p_N and positive in the other. We can observe that, since p_m is not equal to p_n, one of p_M or p_N must assign a nonzero exponent to some prime.
Let γ, μ, and ν be the integer products of g, p_M, and p_N. By hypothesis, γμ = γν, which means that μ = ν. But now we have two prime factorizations (p_M and p_N) of the same number (μ) for which one factorization assigns a positive exponent to some prime, and one factorization assigns an exponent of zero. By our earlier result we know that this is impossible.
----
I needed a lot of symbols, and if I were formally typing this up I'd need more, but it didn't seem like a very difficult proof -- I spent more time typing up this comment than working out the proof. Reading the piece, I see that it is specifically called out:
> We’d be able to see instantly that 23 × 1759 ≠ 53 × 769 if we knew that a product of two non-multiples of 23 was always a non-multiple of 23.
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.
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.
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.
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.
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.
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.)
> 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.
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.
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.
> 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)]:
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.
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 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.)
Therefore, p_m and p_n differ only in the nonzero exponents assigned to their various primes. Let g be the set of primes in p_m and p_n with the minimum exponent assigned by either p_m or p_n, let p_M be p_m with all exponents reduced by the exponent assigned by g, and let p_N be p_n with all exponents reduced by the exponent assigned by g. Observe that the exponent assigned to any prime is either 0 in each, or 0 in one of p_M or p_N and positive in the other. We can observe that, since p_m is not equal to p_n, one of p_M or p_N must assign a nonzero exponent to some prime.
Let γ, μ, and ν be the integer products of g, p_M, and p_N. By hypothesis, γμ = γν, which means that μ = ν. But now we have two prime factorizations (p_M and p_N) of the same number (μ) for which one factorization assigns a positive exponent to some prime, and one factorization assigns an exponent of zero. By our earlier result we know that this is impossible.
----
I needed a lot of symbols, and if I were formally typing this up I'd need more, but it didn't seem like a very difficult proof -- I spent more time typing up this comment than working out the proof. Reading the piece, I see that it is specifically called out:
> We’d be able to see instantly that 23 × 1759 ≠ 53 × 769 if we knew that a product of two non-multiples of 23 was always a non-multiple of 23.
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.