Claim: Every natural number N, N>1, has a unique prime factorization.

i.e. N may be written in exactly one way as N=p1p2p3...pr,
where pi is prime and p1 ≤ p2 ≤ p3 ≤ ... ≤ pr. 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=k1k2...ki, and M=m1m2...mj. But then N would be KM=k1k2...kim1m2...mj, 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=a1a2...ai, and
N=b1b2...bj.
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 a1 > b1 and consider the number
M = N - b1a2...ai = (a1-b1)a2...ai.
M is clearly a smaller number than N.

1. Expand (a1-b1) into primes c1c2...ck so M may be written as

M = c1c2...cka2...ai.

2. Now find M a different way. Use the other prime factorization given for N above:

M = N - b1a2...ai = (b1b2...bj)-(b1a2...ai)
= b1(b2...bj-a2...ai)
= b1d1d2...dl,

where d1d2...dl is the prime factorization of(b2...bj-a2...ai).

We need to show that these two factorizations of M, which is smaller than N, are distinct, to find our contradiction. First observe that b1 does appear in the second factorization. To show that it is not in the first factorization, recall that b1 is not equal to any of the ai in the first factorization. Furthermore, b1 does not divide (a1-b1) because if it did, we could write (a1-b1) = k*b1, or a1 = (k+1)(b1), which contradicts the fact that a1 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.