The fundamental theorem of arithmetic states that for all positive integers except 1, there exists a unique prime factorization. For example, take the number 12. The prime factorization of 12 is 22·3. There is no other combination of prime factors that multiplies out to 12.
There are two things to be proved. Both parts of the proof will use the Well-ordering Principle for the set of natural numbers.
- We first prove that every a > 1 can be written as a product of prime factors. (This includes the possibility of there being only one factor in case a is prime.) Suppose BWOC that there exists a integer a > 1 such that a cannot be written as a product of primes. By the Well-ordering Principle, there is a smallest such a. Then by assumption a is not prime so a = bc where 1 < b; c < a. So b and c can be written as products of prime factors (since a is the smallest positive integer than cannot be.) But since a = bc, this makes a a product of prime factors, a CONTRADICTION.
- Now suppose BWOC that there exists an integer a > 1 that has two different prime factorizations, say a = p1 ... ps = q1 ... qt, where the pi and qj are all primes. (We allow repetitions among the pi and qj. That way, we don't have to use exponents.) Then p1|a = q1 ... qt. Since p1 is prime, by the Lemma above, p1|qj for some j. Since qj is prime and p1 > 1, this means that p1 = qj . For convenience, we may renumber the qj so that p1 = q1. We can now cancel p1 from both sides of the equation above to get p2 ... ps = q2 ... qt. But p2 ... ps < a and by assumption a is the smallest positive integer with a non-unique prime factorization. It follows that s = t and that p2 ... ps are the same as q2 ... qt, except possibly in a different order. But since p1 = q1 as well, this is a CONTRADICTION to the assumption that these were two different factorizations. Thus there cannot exist such an integer a with two different factorizations.
All Math Words Encyclopedia is a service of
Life is a Story Problem LLC.
Copyright © 2005-2011 Life is a Story Problem LLC. All rights reserved.
This work is licensed under a Creative Commons Attribution-Noncommercial-Share Alike 3.0 License