3 ms·

It actually becomes much easier to understand if you approach it from the other direction. Some assumptions - A prime is only evenly divisible by itself and o

It actually becomes much easier to understand if you approach it from the other direction. Some assumptions - A prime is only evenly divisible by itself and one. - One is not a prime. - A composite number is generated by multiplying two or more primes. - No number of primes can be multiplied together to make another prime. That would mean that the so called prime generated is composite. Now, say we have a number n with two different prime factorizations, f1 and f2, where f1 includes a certain prime p, and f2 does not, and where n is evenly divisible by p, and n/p = m. Now, if f1 and f2 are both prime factorizations of n, then consider what happens when we do this: f1 = p * m = f2 m = f2 / p f2 does not contain p, and we cannot construct a prime p from other primes or composites. 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. Therefore f2 cannot be another prime factorization of n. That may not be perfectly rigorous, but I'm certain the gist of it is true.

justinhj 10y ago
I'm no mathematician but this makes sense to me. I'll be interestsd in seeing how the article follow up proves the same.
CarolineW 10y ago
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.
SamReidHughes 10y ago
> f2 does not contain p, and we cannot construct a prime p from other primes or composites. 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. No it doesn't. Suppose p, m, q and r are (distinct) primes where f1 = p * m, f2 = q * r. Then why can't you have (q * r) / p = m? The fundamental theorem of arithmetic says you can't, but you are trying to prove that.
vladsotirov 10y ago
You've correctly shown that "f2 does not contain p". However, the subtle bit of reasoning "f2 cannot be evenly divisible by p as that would require it to have a prime factor of p" is not justified by any of your assumptions. Let me be clear: f2 is a fixed product of primes p_1, p_2, p_3, etc. It is certainly true that each p_i divides evenly f2. What you use, however, is the converse claim: that every prime p that divides f2 is on this list. This converse claim, that "every prime p that divides f2 is on the list of primes that we built f2 out of", does not follow from "no number of primes can be multiplied together to make another prime". The latter implies only that a prime that both divides f2 and can be built out from the given list of primes, has to be on the list of primes. In fact, the converse claim "every prime p that divides f2 is on the list of primes that we built f2 out of" is essentially one variant of the statement of unique prime factorization, so you actually fell into the trap of circular reasoning.
nilkn 10y ago
I'm on the controversial side that Gowers's overall argument is unfair to laymen, but this is indeed a circular argument. It can be modified to make it more robust while keeping the structure of the argument fairly close to what you have here, but it requires a bit more sophistication. Specifically, suppose that n is the smallest integer with two different prime factorizations, and write these factorizations as p_1 * ... * p_n and q_1 * ... * q_m. Now first you might imagine that these two factorizations could be different and yet share at least one prime in common. But this is impossible. If they shared a prime in common, we might as well assume it's the first, so that p_1 = q_1 (i.e., we're just reordering the indices). But then n / p_1 has the two different factorizations p_2 * ... * p_n and q_2 * ... * q_m, but since n / p_1 is smaller than n this is a contradiction. So we can assume that these two factorizations share no primes in common. In particular, we can assume without loss of generality that p_1 < q_1. Consider now the quantity n' = n - p_1 * q_2 * ... * q_m. This is positive but smaller than n. Now we already know that p_1 divides n, so we can actually factor out p_1 here to obtain n' = p_1 * (n / p_1 - q_2 * ... * q_m). This gives us one factorization of n' < n in which p_1 occurs. Now here is the critical observation. Because n' is smaller than n, n' must have a unique factorization due to the choice of n as the smallest number which does not have a unique factorization. (This is the point where the proof will fail for many other more exotic rings which lack the intrinsic well-ordering principle enjoyed by the integers.) But we can also write n' = q_1 * q_2 * ... * q_m - p_1 * q_2 * ... * q_m = (q_1 - p_1) * q_2 * ... * q_m. This is another factorization of n', and by uniqueness it must contain p_1. This is only possible if p_1 divides q_1 - p_1, which is only possible if p_1 divides q_1, which is not possible since q_1 is prime. --- This highlights why I disagree with Gowers here. He's looking at other rings which violate the basic ordered structure of the integers, but this structure plays a critical role in our intuition about the integers, and I believe it's precisely why we feel something like unique factorization is "obvious" (or intuitive) for the positive integers, but it remains very elusive for, say, Z[sqrt(-n)] (where it's true if n = 1,2 and false if n >= 3).

justinhj 10y ago

I'm no mathematician but this makes sense to me. I'll be interestsd in seeing how the article follow up proves the same.

CarolineW 10y ago

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.

SamReidHughes 10y ago

> f2 does not contain p, and we cannot construct a prime p from other primes or composites. 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. No it doesn't. Suppose p, m, q and r are (distinct) primes where f1 = p * m, f2 = q * r. Then why can't you have (q * r) / p = m? The fundamental theorem of arithmetic says you can't, but you are trying to prove that.

vladsotirov 10y ago

You've correctly shown that "f2 does not contain p". However, the subtle bit of reasoning "f2 cannot be evenly divisible by p as that would require it to have a prime factor of p" is not justified by any of your assumptions. Let me be clear: f2 is a fixed product of primes p_1, p_2, p_3, etc. It is certainly true that each p_i divides evenly f2. What you use, however, is the converse claim: that every prime p that divides f2 is on this list. This converse claim, that "every prime p that divides f2 is on the list of primes that we built f2 out of", does not follow from "no number of primes can be multiplied together to make another prime". The latter implies only that a prime that both divides f2 and can be built out from the given list of primes, has to be on the list of primes. In fact, the converse claim "every prime p that divides f2 is on the list of primes that we built f2 out of" is essentially one variant of the statement of unique prime factorization, so you actually fell into the trap of circular reasoning.

nilkn 10y ago

I'm on the controversial side that Gowers's overall argument is unfair to laymen, but this is indeed a circular argument. It can be modified to make it more robust while keeping the structure of the argument fairly close to what you have here, but it requires a bit more sophistication. Specifically, suppose that n is the smallest integer with two different prime factorizations, and write these factorizations as p_1 * ... * p_n and q_1 * ... * q_m. Now first you might imagine that these two factorizations could be different and yet share at least one prime in common. But this is impossible. If they shared a prime in common, we might as well assume it's the first, so that p_1 = q_1 (i.e., we're just reordering the indices). But then n / p_1 has the two different factorizations p_2 * ... * p_n and q_2 * ... * q_m, but since n / p_1 is smaller than n this is a contradiction. So we can assume that these two factorizations share no primes in common. In particular, we can assume without loss of generality that p_1 < q_1. Consider now the quantity n' = n - p_1 * q_2 * ... * q_m. This is positive but smaller than n. Now we already know that p_1 divides n, so we can actually factor out p_1 here to obtain n' = p_1 * (n / p_1 - q_2 * ... * q_m). This gives us one factorization of n' < n in which p_1 occurs. Now here is the critical observation. Because n' is smaller than n, n' must have a unique factorization due to the choice of n as the smallest number which does not have a unique factorization. (This is the point where the proof will fail for many other more exotic rings which lack the intrinsic well-ordering principle enjoyed by the integers.) But we can also write n' = q_1 * q_2 * ... * q_m - p_1 * q_2 * ... * q_m = (q_1 - p_1) * q_2 * ... * q_m. This is another factorization of n', and by uniqueness it must contain p_1. This is only possible if p_1 divides q_1 - p_1, which is only possible if p_1 divides q_1, which is not possible since q_1 is prime. --- This highlights why I disagree with Gowers here. He's looking at other rings which violate the basic ordered structure of the integers, but this structure plays a critical role in our intuition about the integers, and I believe it's precisely why we feel something like unique factorization is "obvious" (or intuitive) for the positive integers, but it remains very elusive for, say, Z[sqrt(-n)] (where it's true if n = 1,2 and false if n >= 3).