Theorem 8.5: (The Fundamental Theorem of Arithmetic)
Existence: Every natural number greater than 1 is either prime or can be written as a product of primes.
Uniqueness: Any factorization into a product of primes will involve the same number of the same prime factors.
Proof: (Existence) Suppose that there is a natural number n > 1 which is neither prime nor can be written as a product of primes. Then
is a non empty set of natural numbers. By Theorem 5.1, the Well Ordering Principle, there exists a smallest element of this set. Call it m. Since m is not prime, it can be expressed as a product of two smaller natural numbers
where s and t are natural numbers which are smaller than m. Since m is the smallest natural number which is neither prime nor a product of primes, both s and t must be either prime or a product of primes. In either case, m will be a product of primes.
(Uniqueness) Suppose that there is a natural number n > 1 which can be written as a product of primes in two different ways. Then
is a nonempty set of natural numbers. By Theorem 5.1, the Well Ordering Principle, there exists a smallest element of this set. Call it m. Then m has two different prime factorizations
where the pi and qj are primes. We can assume, after perhaps relabeling, that r < s.
Either p1 = q1 or it doesn't. If it doesn't, then since p1 is prime and its only divisors are 1 and itself, if it is not equal to q1, then the greatest common divisor of p1 and q1 is 1, so they are relatively prime. By Theorem 8.3, it follows that p1 divides the product of the rest of the q's. By repeating the argument we just made, either p1 is equal to q2 or it will divide the product of the rest of the q's. We conclude that p1 is equal to one of the q's say, qj. We thus have
By Theorem 7.10, the Cancellation Property of Multiplication of Natural Numbers,
Since m = rp1, and p1, being prime is, by Definition 8.4, greater than 1, so by Theorem 7.8, r < m and so by the definition of m, the two prime factorizations of r, hence m, must be the same.