Claim: Every
natural number N, N>1, has a unique
prime factorization.
i.e. N may be written in exactly one way as N=p
1p
2p
3...p
r,
where p
i is prime and p
1 ≤ p
2 ≤ p
3 ≤ ... ≤ p
r.
Note: WLOG, we are ordering the prime numbers in order of their magnitude. They may, course, be ordered in any way we choose, and several of the prime numbers may be equal. For example, 100=2*2*5*5. We simply seek to place the primes in some standard order.
Proof: First, we'll show that any
natural number N>1 can be written as a product of prime numbers.
Assume that N
cannot be written as a product of prime numbers. Let N be the first number which cannot be written as a product of one or more primes. (Thus, all smaller numbers may be written as products of primes). N, therefore, is not
prime, or it would already be a product of prime numbers. N must be divisible by some number 1 < K < N and we may write N=KM. Since both K and M are smaller than N, they may be written as products as primes:
K=k
1k
2...k
i, and M=m
1m
2...m
j. But then N would be KM=k
1k
2...k
im
1m
2...m
j, which is a product of prime numbers, contradicting our
assumption.
Therefore, all natural numbers may be written as products of primes.
Now that we know all natural numbers may somehow be
factored into primes, let's suppose that there are some natural numbers which may be factored into primes at least two distinct ways. Let's choose some N which is the smallest number which may be factored into primes 2 different ways. Let these 2 prime factorizations be:
N=a
1a
2...a
i, and
N=b
1b
2...b
j.
Please note that these two factorizations have
no primes in common. If they did, we would divide them out and get two equal factorizations of an even smaller number, but N is the smallest number with two distinct factorizations, so this is not possible.
Assume a
1 > b
1 and consider the number
M = N - b
1a
2...a
i = (a
1-b
1)a
2...a
i.
M is clearly a smaller number than N.
1. Expand (a
1-b
1) into primes c
1c
2...c
k so M may be written as
M = c
1c
2...c
ka
2...a
i.
2. Now find M a different way. Use the other prime
factorization given for N above:
M = N - b
1a
2...a
i = (b
1b
2...b
j)-(b
1a
2...a
i)
= b
1(b
2...b
j-a
2...a
i)
= b
1d
1d
2...d
l,
where d
1d
2...d
l is the prime factorization of(b
2...b
j-a
2...a
i).
We need to show that these two factorizations of M, which is smaller than N, are distinct, to find our contradiction. First observe that b
1 does appear in the second factorization. To show that it is
not in the first factorization, recall that b
1 is not equal to any of the a
i in the first factorization. Furthermore, b
1 does not divide (a
1-b
1) because if it did, we could write (a
1-b
1) = k*b
1, or a
1 = (k+1)(b
1), which contradicts the fact that a
1 is prime. Therefore it cannot appear among the d's. Thus these two prime factorizations of M are
distinct. This contradicts our
assumption that N was the smallest such number.
Since there is no smallest number with two
distinct prime factorizations, by the Well-Ordering Principle of the Natural Numbers (aka the
Well Ordering Theorem), there must be no such numbers.
Taken from homework assignment from class titled "Fundamental Properties of Spaces and Functions: Part 1" at the University of Iowa, 2002.