Every natural number
N, N>1, has a unique prime factorization
i.e. N may be written in exactly one way as N=p1
is prime and p1
≤ ... ≤ 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.
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:
, and M=m1
. But then N would be KM=k1
, 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 factor
ed 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:
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.
and consider the number
M = N - b1
M is clearly a smaller number than N.
1. Expand (a1
) into primes c1
so M may be written as
M = c1
2. Now find M a different way. Use the other prime factorization
given for N above:
M = N - b1
is the prime factorization of(b2
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
) because if it did, we could write (a1
) = k*b1
, or a1
), 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.