6 ms·

Wouldn't multiple possible factorizations require numbers that both are and aren't divisible by certain numbers? If it's divisible by a number, the number must

Wouldn't multiple possible factorizations require numbers that both are and aren't divisible by certain numbers? If it's divisible by a number, the number must appear in its factorization and vice versa.

ColinWright 10y ago
Wouldn't multiple possible factorizations require numbers that both are and aren't divisible by certain numbers? Yes. If it's divisible by a number, the number must appear in its factorization and vice versa. That is what the FTA says, so you are saying that the FTA is true, but that's just saying that you believe it. The article is trying to point out why once you know enough about how arithmetic works,it's no longer obvious. In particular, there are fairly natural rings that look very similar to the integers, but where this is not true. Taking the example in the linked article, it's true if we extend the integers by sqrt(-1), but it's not true if we extend the integers by sqrt(-5). In that ring we have: 2 x 3 = (1 + sqrt(-5))x(1 - sqrt(-5)) So (1 + sqrt(-5)) appears in one factorisation of 6, but not in another. So in this case, factorisations are not unique.
- deleted 10y ago
  [deleted]
- bluecalm 10y ago
  Obvious is different than easy to prove. The concepts of multiplication, division, prime number and "divisible by" are much older than formal proofs and arbitrary sets of axioms. Let's say I only now what multiplication is and that AxB = BxA and that prime number can't be written as AxB unless A or B are 1. Now it's obvious that there are factorings of a number: you just divide it by smallest possible prime divider until you reach 1, that process obviously terminates every time and produces a finite factoring. Now let's assume that our number A has two factorings F1 and F2. Let's sort them from the smallest to the biggest divider. Is it possible that F1 and F2 are different at the first position? It isn't as that would mean the same number has different smallest prime divider. We therefore divide our number by the prime divider at that first position and continue the process proving that dividers at all the positions must be the same or that F1 F2 are factorings of a different number. It is in fact obvious to someone who understands multiplication. As to some points from the article: >>it is obvious that 23\times 1759 is not the same number as 53\times 769. It is, we sort them from the smallest to bigger prime in the factorization. If they were the same number that would mean the same number's smallest prime diviser is 23 and 53 at the same time. You may want to argue that it's not obvious that to be divisible by a prime number it must appear in a factorization - here I just assume you understand it's obvious for anyone who knows what multiplication is and that the fact that it's not obvious to your system with your axioms is your problem altogether. >>If it’s so obvious that every number has a unique factorization, then why is the corresponding statement false in a similar context? It's not a similar context, at least for non-mathematician. You are introducing some weird objects in the form of a + b*sqrt(-5). I may not even understand the concept of a complex number but I still can understand FTA. Btw, for that FTA isn't obvious because there is no order for those objects, it's not clear what is bigger or smaller than something else and which position given object is in if we sort them from the smallest. I get it: FTA is hard to prove in your nice formal system with your nifty arbitrary chosen axioms and formal deduction rules. It's bloody obvious to the caveman who can do multiplication by putting stones in a rectangle though.
  - ColinWright 10y ago
    > Now let's assume that our number A has > two factorings F1 and F2. Let's sort > them from the smallest to the biggest > divider. OK, I've done that. > Is it possible that F1 and F2 are > different at the first position? It > isn't as that would mean the same > number has different smallest prime > divider. So why is this false in Z[ sqrt(-5) ] ?? There we have: 6 = 2 x 3 6 = (1 - sqrt(-5)) x ((1 + sqrt(-5)) Now 6 has a "smallest" factor of 2, and a "smallest" factor of (1 - sqrt(-5)). > It is in fact obvious to someone who > understands multiplication. So you are claiming that the author of the linked article, Prof Sir Tim Gowers, winner of the Fields Medal, Fellow of the Royal Society, doesn't understand multiplication? Might I instead suggest that you don't understand the things that might go wrong, and the subtleties that lurk underneath.
    - bluecalm 10y ago
      >>So why is this false in Z[ sqrt(-5) ] I don't know, I don't know what sqrt is, let alone sqrt for a negative number. It's like asking someone who made a nice geometric proof of Pitagoras theorem why it doesn't work on a 4 dimensional sphere for stuff which is kinda like triangles. It's different multiplication you are mentioning here. I can't do (1-sqrt(-5) x (1 + sqrt(-5) by putting some stones in a rectangle and counting them. The concepts of primes, multiplication, divisor don't instantly make sense for those objects and I am not sure why you ask me to extend them. I am just claiming FTA is obvious for natural numbers and straightforward multiplication. >> 6 = 2 x 3 >> 6 = (1 - sqrt(-5)) x ((1 + sqrt(-5)) I mentioned sorting from the smallest, can't do that with your sqrt thing. Another obvious thing with multiplication is that the more you multiply the more you get which isn't true for a + sqrt(-5). >>So you are claiming that the author of the linked article, Prof Sir Tim Gowers, winner of the Fields Medal, Fellow of the Royal Society, doesn't understand multiplication? No, I haven't claimed that. I think FTA is quite obvious to him but it's not obvious if you try formally define arithmetic using the smallest sensible subset of axioms. It is obvious is you just understand multiplication and can perform it by forming rectangles and then rectangles from rectangles (in case of 3 terms to multiply). >>ight I instead suggest that you don't understand the things that might go wrong, and the subtleties that lurk underneath. There are many subtleties in defining and proving things formally. That's a different point altogether.
pathsjs 10y ago
> If it's divisible by a number, the number must appear in its factorization and vice versa. By writing "its" factorization, you are already assuming that there is only one
umanwizard 10y ago
The linked article gives an example, in the ring Z[sqrt(-5)]. 6 is divisible by 2. However, "the" (really "a") prime factorization of 6 is (1+sqrt(-5)) * (1-sqrt(-5)), in which 2 does not appear. So your assertion that "if it's divisible by a number, the number must appear in its factorization" is not true in all rings.
Chinjut 10y ago
Who says "if it's divisible by a number, the number must appear in its factorization"? Why is that true? For example, 24 is divisible by 6, though 24 has the prime factorization 2 * 2 * 2 * 3, with no 6 to be found. "Right, but all the prime factors of 6 appear in the prime factorization of 24. If X is divisible by the prime p, then there is a unique prime factorization of X, which must include a factor of p", you may reply. Well, this is the non-obvious fact. If you don't already know for certain that prime factorizations are unique (and this is the claim in contention), then it's not obvious why X couldn't have multiple prime factorizations, some including p directly and some not including p directly even though p ends up dividing the overall product. The non-obvious fact is that a prime can't divide a product unless it divides one of the factors. Why should that be true? (It IS true of the integers, but it's NOT true of other very similar structures. The reason it's true of the integers, the special property that makes the whole thing tick, is, ultimately, that Euclid's algorithm shows us how the values not divisible by prime p are in fact invertible modulo p (and vice versa), so that the values not divisible by p are closed under multiplication. But that's not at all immediately obvious!)
- PepeGomez 10y ago
  No other prime is divisible by 3 than 3 itself and so on. And you can't ever get a number divisible by 3 by multiplying numbers that are not divisible by 3. (3n-1) * m mod 3 and (3n-2) * m mod 3 cycle predictably and never become zero unless m mod 3 = 0. The same principle should hold for every number.
  - schoen 10y ago
    The mod-cycling-predictably property also holds for composite numbers, while I think the "can't get a number divisible by 3 by multiplying numbers that are not divisible by 3" part relies on the fundamental theorem of arithmetic! (Otherwise, how do we know that you can't get a number divisible by 3 by multiplying numbers that are not divisible by 3, yet the same doesn't hold for 4? I think that's the fundmental theorem of arithmetic back again in another guise.)
    - 10y ago

ColinWright 10y ago

Wouldn't multiple possible factorizations require numbers that both are and aren't divisible by certain numbers? Yes. If it's divisible by a number, the number must appear in its factorization and vice versa. That is what the FTA says, so you are saying that the FTA is true, but that's just saying that you believe it. The article is trying to point out why once you know enough about how arithmetic works,it's no longer obvious. In particular, there are fairly natural rings that look very similar to the integers, but where this is not true. Taking the example in the linked article, it's true if we extend the integers by sqrt(-1), but it's not true if we extend the integers by sqrt(-5). In that ring we have: 2 x 3 = (1 + sqrt(-5))x(1 - sqrt(-5)) So (1 + sqrt(-5)) appears in one factorisation of 6, but not in another. So in this case, factorisations are not unique.

deleted 10y ago
[deleted]
bluecalm 10y ago
Obvious is different than easy to prove. The concepts of multiplication, division, prime number and "divisible by" are much older than formal proofs and arbitrary sets of axioms. Let's say I only now what multiplication is and that AxB = BxA and that prime number can't be written as AxB unless A or B are 1. Now it's obvious that there are factorings of a number: you just divide it by smallest possible prime divider until you reach 1, that process obviously terminates every time and produces a finite factoring. Now let's assume that our number A has two factorings F1 and F2. Let's sort them from the smallest to the biggest divider. Is it possible that F1 and F2 are different at the first position? It isn't as that would mean the same number has different smallest prime divider. We therefore divide our number by the prime divider at that first position and continue the process proving that dividers at all the positions must be the same or that F1 F2 are factorings of a different number. It is in fact obvious to someone who understands multiplication. As to some points from the article: >>it is obvious that 23\times 1759 is not the same number as 53\times 769. It is, we sort them from the smallest to bigger prime in the factorization. If they were the same number that would mean the same number's smallest prime diviser is 23 and 53 at the same time. You may want to argue that it's not obvious that to be divisible by a prime number it must appear in a factorization - here I just assume you understand it's obvious for anyone who knows what multiplication is and that the fact that it's not obvious to your system with your axioms is your problem altogether. >>If it’s so obvious that every number has a unique factorization, then why is the corresponding statement false in a similar context? It's not a similar context, at least for non-mathematician. You are introducing some weird objects in the form of a + b*sqrt(-5). I may not even understand the concept of a complex number but I still can understand FTA. Btw, for that FTA isn't obvious because there is no order for those objects, it's not clear what is bigger or smaller than something else and which position given object is in if we sort them from the smallest. I get it: FTA is hard to prove in your nice formal system with your nifty arbitrary chosen axioms and formal deduction rules. It's bloody obvious to the caveman who can do multiplication by putting stones in a rectangle though.
- ColinWright 10y ago
  > Now let's assume that our number A has > two factorings F1 and F2. Let's sort > them from the smallest to the biggest > divider. OK, I've done that. > Is it possible that F1 and F2 are > different at the first position? It > isn't as that would mean the same > number has different smallest prime > divider. So why is this false in Z[ sqrt(-5) ] ?? There we have: 6 = 2 x 3 6 = (1 - sqrt(-5)) x ((1 + sqrt(-5)) Now 6 has a "smallest" factor of 2, and a "smallest" factor of (1 - sqrt(-5)). > It is in fact obvious to someone who > understands multiplication. So you are claiming that the author of the linked article, Prof Sir Tim Gowers, winner of the Fields Medal, Fellow of the Royal Society, doesn't understand multiplication? Might I instead suggest that you don't understand the things that might go wrong, and the subtleties that lurk underneath.
  - bluecalm 10y ago
    >>So why is this false in Z[ sqrt(-5) ] I don't know, I don't know what sqrt is, let alone sqrt for a negative number. It's like asking someone who made a nice geometric proof of Pitagoras theorem why it doesn't work on a 4 dimensional sphere for stuff which is kinda like triangles. It's different multiplication you are mentioning here. I can't do (1-sqrt(-5) x (1 + sqrt(-5) by putting some stones in a rectangle and counting them. The concepts of primes, multiplication, divisor don't instantly make sense for those objects and I am not sure why you ask me to extend them. I am just claiming FTA is obvious for natural numbers and straightforward multiplication. >> 6 = 2 x 3 >> 6 = (1 - sqrt(-5)) x ((1 + sqrt(-5)) I mentioned sorting from the smallest, can't do that with your sqrt thing. Another obvious thing with multiplication is that the more you multiply the more you get which isn't true for a + sqrt(-5). >>So you are claiming that the author of the linked article, Prof Sir Tim Gowers, winner of the Fields Medal, Fellow of the Royal Society, doesn't understand multiplication? No, I haven't claimed that. I think FTA is quite obvious to him but it's not obvious if you try formally define arithmetic using the smallest sensible subset of axioms. It is obvious is you just understand multiplication and can perform it by forming rectangles and then rectangles from rectangles (in case of 3 terms to multiply). >>ight I instead suggest that you don't understand the things that might go wrong, and the subtleties that lurk underneath. There are many subtleties in defining and proving things formally. That's a different point altogether.

pathsjs 10y ago

> If it's divisible by a number, the number must appear in its factorization and vice versa. By writing "its" factorization, you are already assuming that there is only one

umanwizard 10y ago

The linked article gives an example, in the ring Z[sqrt(-5)]. 6 is divisible by 2. However, "the" (really "a") prime factorization of 6 is (1+sqrt(-5)) * (1-sqrt(-5)), in which 2 does not appear. So your assertion that "if it's divisible by a number, the number must appear in its factorization" is not true in all rings.

Chinjut 10y ago

Who says "if it's divisible by a number, the number must appear in its factorization"? Why is that true? For example, 24 is divisible by 6, though 24 has the prime factorization 2 * 2 * 2 * 3, with no 6 to be found. "Right, but all the prime factors of 6 appear in the prime factorization of 24. If X is divisible by the prime p, then there is a unique prime factorization of X, which must include a factor of p", you may reply. Well, this is the non-obvious fact. If you don't already know for certain that prime factorizations are unique (and this is the claim in contention), then it's not obvious why X couldn't have multiple prime factorizations, some including p directly and some not including p directly even though p ends up dividing the overall product. The non-obvious fact is that a prime can't divide a product unless it divides one of the factors. Why should that be true? (It IS true of the integers, but it's NOT true of other very similar structures. The reason it's true of the integers, the special property that makes the whole thing tick, is, ultimately, that Euclid's algorithm shows us how the values not divisible by prime p are in fact invertible modulo p (and vice versa), so that the values not divisible by p are closed under multiplication. But that's not at all immediately obvious!)

PepeGomez 10y ago
No other prime is divisible by 3 than 3 itself and so on. And you can't ever get a number divisible by 3 by multiplying numbers that are not divisible by 3. (3n-1) * m mod 3 and (3n-2) * m mod 3 cycle predictably and never become zero unless m mod 3 = 0. The same principle should hold for every number.
- schoen 10y ago
  The mod-cycling-predictably property also holds for composite numbers, while I think the "can't get a number divisible by 3 by multiplying numbers that are not divisible by 3" part relies on the fundamental theorem of arithmetic! (Otherwise, how do we know that you can't get a number divisible by 3 by multiplying numbers that are not divisible by 3, yet the same doesn't hold for 4? I think that's the fundmental theorem of arithmetic back again in another guise.)
  - 10y ago