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.
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.
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.
> 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.
I really appreciate your patient engagement with the doubters in this thread, but I think that your determination to make your point has led you astray here.
> Now 6 has a "smallest" factor of 2, and a "smallest" factor of (1 - sqrt(-5)).
As [nilkn](https://news.ycombinator.com/item?id=11955341) mentioned upthread, if you consider well ordering part of the intuition of the positive integers, then you have (depending on what else you consider obvious) practically pinned down the integers already. This reference to the 'smallest' factor is not just a throwaway, and it sinks this example (why is 1 - sqrt(-5) smaller than 1 + sqrt(-5), for example?).
> 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?
This gives the impression that math is subject to an appeal to authority, which I think is a shame. The newest student can find the error in the work of the Fields Medallist—though he or she probably won't, and the error he or she seems to have found is more likely to be a concealed subtlety—and to suggest avoiding dissenting on the grounds of eminence gives entirely the wrong idea of how mathematical argument should proceed.
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.
You're approaching this with a hostile attitude, which is preventing you from understanding and/or addressing what other people are saying, and substituting (light) mockery for attempts to understand what others are saying. You're not going to learn anything or convince anybody of anything this way.
The point of using the ring with the sqrt in it is to conveniently demonstrate that the FTA is non-obvious. Since it is only being used for demonstration, and not as part of a proof, faking ignorance of sqrts and imaginary numbers is not helpful to you. There are many things in mathematics where the subtleties only came out later; heck, that's basically the entire history of set theory. Sets are also trivial if you come at them with an attitude of artificial ignorance like that.
But he clearly does understand, and some gentle mockery at the other side is called for when they play dumb.
I'm sure the fundamental theorem of arithmetic has a non-obvious proof. And perhaps that's precisely what a mathematician means every time they say "non-obvious". If that were all just made explicit to this general interest site in the first place, perhaps we'd have nothing to discuss.
But if we are trying to play coy here, 1+1=2 also requires a non-obvious proof to anyone not versed in formal methods. I looked a proof up:
I don't know how long it would take me, working alone, to come up with that proof. It's non-obvious because it took humans probably 100,000 years to come up with it, even though we've had the IQ to do it for a long time. I don't think we could agree on what constitutes a proof of it without some social aspect and convention, so non-obvious by means of proof.
But, we've been using and making predictions about the world using 1+1=2 for very much longer. That seems like a pretty worthwhile definition of obvious.
>>You're not going to learn anything or convince anybody of anything this way.
The tone of the original article is light mockery as well. That's why I am imitating it. I think the author is wrong, it's quite condescending for you to say "you are not going to learn". What about pointing the non-obvious step in the simple reasoning I gave?
>>The point of using the ring with the sqrt in it is to conveniently demonstrate that the FTA is non-obvious.
This is not a correct way to point something is non-obvious. I illustrated why already. It's just not a correct way of arguing.
>>Since it is only being used for demonstration, and not as part of a proof, faking ignorance of sqrts and imaginary numbers is not helpful to you.
It is. It points out why the argument made in the blog post is not correct way to argue something is non-obvious.
>>There are many things in mathematics where the subtleties only came out later; heck, that's basically the entire history of set theory. Sets are also trivial if you come at them with an attitude of artificial ignorance like that.
Some things in set theory are trivial, some aren't. I don't understand your point here. I am claiming FTA is obvious when it comes to natural numbers not that something similar to FTA on some other objects is obvious.
>>So what you are saying is that if you don't know what can go wrong then it's "obviously true."
I never claimed that. I only claimed that FTA is obvious and that pointing out that something similar to FTA on some complex objects (a + sqrt(-5) things) doesn't work isn't a correct way to argue the FTA itself isn't obvious.
>>If you draw a distorted circle in the plane then it's obviously true that it has an inside and an outside.
Yes (as long as definition of "distorted" doesn't contain any surprises, I am assuming you mean not exactly a circle but something like it).
>>The inside is obviously contractable to a point, and the outside is obviously contractable to a plane with a hole in it.
Those things already aren't obvious. Go ask someone a bright kid in high school what "contractable to a plane" is. It's not obvious in any way to non-mathematician.
I am claiming FTA is obvious for a bright person who understand multiplication (or for a caveman who can do multiplication by putting rectangles together, then making rectangles from those rectangles etc.)
>>In three dimensions if you have a distorted sphere then it obviously divides space into an inside and an outside.
Yes, obvious.
>>The inside is obviously contractable to a point, and the outside is obviously contractable to 3D space with a hole in it
Again, those things are very far from obvious. What "contractable to 3D space with a hole" means is very far away from "obvious" by any reasonable definition of the word.
The correct spelling "contractible" yields useful Google results, namely that spheres in 3 dimensions (point 4) are not contractible to a single point.
Edit: ... and maybe circles (point 2) too? Not a mathematician.
> The correct spelling "contractible" yields useful Google results, namely that spheres in 3 dimensions (point 4) are not contractible to a single point.
The claim is about the interior, not the sphere itself (which certainly is not contractible, as you say).
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!)
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.
You're right that there's only so many possible nonzero remainders mod 3, and you can check for yourself that if you multiply any of them together, you end up with another non-multiple of 3.
The same is true for 5: it takes a little more time to check, since there are a few more possible remainders mod 5, but it happens to be true, and so you can indeed verify, that when you multiply non-multiples of 5 together, the result is also a non-multiple of 5.
And you can go ahead and check by brute force that this is true of 7, and 11, and 13 as well. Mod any of those, when you multiply nonzero values, you get a nonzero result. Any modulus this happens to be true of, you can sit down and verify that it's true of, by just checking all the finitely many cases.
But knowing it's true of the first few primes doesn't guarantee the same fact will be true of every other prime you check.
How do we know that this is in fact the case for every prime?
It's not true of every number, after all: 4 isn't divisible by 10, and 5 isn't divisible by 10, and yet 4 * 5 is divisible by 10. 10 doesn't have the property that it only divides a product if it divides one of the factors.
So why do primes have this property? Obviously, if 0 < A, B < p, you can't get A * B = p right on the dot (by the relevant definition of "prime"), but why can't it be the case that A * B = some multiple of p?
This is a non-obvious fact. This is where the Euclidean algorithm reasoning invoked above comes in. It doesn't just follow immediately.
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.)
It seems a bit tricky to do so without proving the fundamental theorem along the way, given another commenter's observation that the same principle doesn't hold for divisibility by composite numbers (you can get 726=22×33, where 726 is divisible by 6 yet neither 22 nor 33 is).
No other prime is divisible by (1-sqrt(-5)) than (1-sqrt(-5)) itself, and yet you can multiply other numbers together and get a number divisible by (1-sqrt(-5)), namely 2 and 3 to get 6.
Why? How do we know factorizations are unique? That is the claim under contention. That is precisely what Gowers in the original article is noting as non-obvious [but often mistakenly taken to be obvious].
If we don't already know (prime) factorizations are unique, how do we know that, if an integer is divisible by a prime, that prime must appear in every possible factorization of that integer?
"Prime factorizations are unique" is equivalent, in a straightforward way, to "If p is a prime factor of x, then p appears in every prime factorization of x". It's easy to deduce either of these from the other. But neither of these statements is obviously true.
They turn out to be true for the integers, but seeing why they are true requires an extra, not at all obvious insight (the reasoning invoked above via the Euclidean algorithm).
Alright. I guess I misunderstood what you were getting at with your comment. And perhaps you misunderstood the nature of my conversation with PepeGomez? You appeared to be correcting me over some misunderstanding I never evinced.
PepeGomez claimed "If it's divisible by a number, the number must appear in its factorization and vice versa." in apparent support of the argument that uniqueness of prime factorizations is therefore obvious.
In response to this, I wrote my initial comment. When, in it, I asked "Who says 'if it's divisible by a number, the number must appear in its factorization'? Why is that true?", that was in response to PepeGomez, a rhetorical way of engaging with the claim they made.
I further noted in my comment that this claim about divisibility and factorizations wasn't quite correct for arbitrary numbers, but was true for prime numbers, but is nonetheless non-obvious for prime numbers. It appears you agree with me on all of this, so... great.
