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 2^{2}·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 integer 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 product of prime factors, a CONTRADICTION.
- Now suppose BWOC that there exists an integer a > 1 that has two different prime factorizations, say a = p_{1} ... p_{s} = q_{1} ... q_{t}, where the p_{i} and q_{j} are all primes. (We allow repetitions among the p_{i} and q_{j}. That way, we don't have to use exponents.) Then p_{1}|a = q_{1} ... q_{t}. Since p_{1} is prime, by the Lemma above, p_{1}|q_{j} for some j. Since q_{j} is prime and p_{1} > 1, this means that p_{1} = q_{j}. For convenience, we may renumber the q_{j} so that p_{1} = q_{1}. We can now cancel p_{1} from both sides of the equation above to get p_{2} ... p_{s} = q_{2} ... q_{t}. But p_{2} ... p_{s} < a and by assumption a is the smallest positive integer with a non-unique prime factorization. It follows that s = t and that p_{2} ... p_{s} are the same as q_{2} ... q_{t}, except possibly in a different order. But since p_{1} = q_{1} 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.^{[1]}
# | A | B | C | D |
E | F | G | H | I |
J | K | L | M | N |
O | P | Q | R | S |
T | U | V | W | Y |
Z | X |
All Math Words Encyclopedia is a service of
Life is a Story Problem LLC.
Copyright © 2018 Life is a Story Problem LLC. All rights reserved.
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License