Hacker News new | past | comments | ask | show | jobs | submit login

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.)


You could probably build that up from the peano axioms and the definition of multiplication and divisibility.


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.


> Who says "if it's divisible by a number, the number must appear in its factorization"? Why is that true?

No one.

If an integer is divisible by a prime then that number must appear in it's unique factorization.


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).


> That is the claim under contention

no, whether or not it is obvious is under contention. I hope no one doubts what I said.

I also never said it's obvious, I said the statement

> if it's divisible by a number, the number must appear in its factorization

isn't true, and wouldn't be claimed.


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.




Guidelines | FAQ | Support | API | Security | Lists | Bookmarklet | Legal | Apply to YC | Contact

Search: