Proofs that Every Natural Number Factors into Only One Unique Product of Primes
Date: 03/15/2012 at 00:16:30 From: Andy Subject: Why does a number have exactly one set of prime factors Why does a number have exactly one set of prime factors? If I look at 100, and find that it factors to 2 x 2 x 5 x 5, then why is that the ONLY set of prime factors that can multiply out to get there? How do I know that it can't be divisible by 3, say? or by 7? By far the most confusing thing is that this principle is so ingrained into our thinking that when I try to construct a proof, I find that I'm using the thing I'm proving within the proof, itself! For example, I can look at a rectangle of 3 x 7 silver balls and know that if I try to divide it by 2, it won't work. Why? Because neither 3 nor 7 is an even number. Ah, but the thinking behind that is: because 2 is not a factor of 3 or 7, therefore the product of 3 x 7 cannot have 2 as a factor. You see? I end up USING that fact in trying to prove it. I dream of attempting something very hard -- namely, explaining Public Key Cryptography simply enough that interested adults and older children would understand it. Key to this is how a number which is the product of two large primes has no other factors. And even though it should be simple, I can't explain it without begging the question. A "layman's" answer, which showed it in graphical terms without being necessarily watertight mathematically, would be great.
Date: 03/15/2012 at 06:10:56 From: Doctor Jacques Subject: Re: Why does a number have exactly one set of prime factors Hi Andy, That is a very good question! The property you mention is known as the Fundamental Theorem of Arithmetic: every natural number greater than 1 is the product of prime numbers in an essentially unique way. This is often taken for granted, but as you found out, this is not obvious at all. (In fact, a similar statement can be false in other mathematical structures.) This was proved by Euclid as proposition 14 of book IX, as described here: http://aleph0.clarku.edu/~djoyce/java/elements/bookIX/propIX14.html To a contemporary mind, however, Euclid's proof is rather hard to follow. For starters, it requires proving all the propositions used in the proof (most of them are in book VII). I will attempt to sketch a simpler proof. The key lemma begins with a prime number p, and positive integers a and b. I will use the symbol "|" to mean "divides." If p | ab, then p | a or p | b (This is, in fact, Euclid's proposition VII.30.) Once we have proved this, the result you seek follows easily: if the prime p divides the product (q_1*...*q_n), where the q_i are prime (not necessarily distinct), then p divides the product q_1*(q*2*...*q_n) Our lemma tells us that either p | q_1, in which case p = q_1 because q_1 is prime; or p divides the other factor (q*2*...*q_n), and we can repeat the argument until there is only one prime left, which will be p. Let us go back to our lemma. Assume that there is a prime p and two integers a and b such that p | ab, and p divides neither a nor b. Note that we can assume that a and b are both greater than 1; indeed, if a = 1, then p | b, and we are done. Consider a fixed prime p, and the set of all the products ab that would be counter-examples, i.e., the set of all numbers of the form ab which are multiples of p and such that neither a nor b is a multiple of p. If there is at least one counter-example, then there must be a smallest counter-example, i.e., a product ab with the smallest possible value. Assume now that ab is such a smallest counter-example (a and b need not be unique, but the product ab is as small as possible). I must emphasize that, if any counter-example exists, then a smallest counter-example must exist: the choice of ab is legitimate, and this is essential, since this will be used to produce a contradiction. We note first that a and b must be smaller than p. Indeed, if a > p, then this integer is also a multiple of p (since ab and bp are): (a - p)b = ab - bp This is smaller than ab, and p divides neither b (by hypothesis) nor (a - p) (since otherwise p would divide a). This shows that (a - p)b is a smaller counter-example, and contradicts our choice of ab as the smallest counter-example. So far, we have proved that 1 < a, b < p. Since a < p, we can consider the greatest multiple of a, call it ka, that is smaller than p. Let c = p - ka (c is actually the remainder of the division of p by a). Now, * c > 0 (otherwise we would have ka = p, which is impossible since p is prime and 1 < a < p) * c < a (otherwise we could replace k by k + 1) * p does not divide c, because 0 < c < a < p * p divides cb = (p - ka)b = pb - k(ab), since p divides pb (obviously) and ab (by hypothesis) Taken together, these properties show that cb is a smaller counter-example than ab, and this contradicts our choice of ab. As this choice is always possible if any counter-example exists, we conclude that such a counter-example does not exist. Please feel free to write back if you require further assistance. - Doctor Jacques, The Math Forum http://mathforum.org/dr.math/
Date: 03/15/2012 at 16:47:09 From: Andy Subject: Thank you (Why does a number have exactly one set of prime factors) Thank you very much for the complete answer! I had a feeling that it was probably one of the fundamental principles of mathematics, but there weren't enough "unique words" in the problem for me to search for it on Google. I was hoping to totally grasp it before thanking you, but to be honest, although I see all the steps, I can't say that I've "got my brain round it," as they say. But I'm confident that I will; and if I wait any longer, you'll think I'm ungracious! In fact, now I know what it is, thanks to you, I can probably search for other explanations if I get stuck. Thank you very much for your time!
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.