7 ms·

In math school we had a saying: "obvious means easy to prove". So the problem is about recognizing the difference between proofs and non-proofs. The hard but sa

In math school we had a saying: "obvious means easy to prove". So the problem is about recognizing the difference between proofs and non-proofs. The hard but satisfying way to learn that difference is to start with axioms. Take some simple system of axioms that holds for Z, and try to prove the FTA from these axioms alone. Then check that the axioms aren't satisfied by Z[sqrt(-5)], or the even numbers, or some other ring where the FTA doesn't hold.

thaumasiotes 10y ago
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.
- ColinWright 10y ago
  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.
  - evanpw 10y ago
    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).
    - deleted 10y ago
      [deleted]
    - ColinWright 10y ago
      ... 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.

thaumasiotes 10y ago

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.

ColinWright 10y ago
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.
- evanpw 10y ago
  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).
  - deleted 10y ago
    [deleted]
  - ColinWright 10y ago
    ... 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.