Use strong mathematical induction to prove the existence part of the unique factorization of integers theorem (Theorem 4.4.5). In other words, prove that every integer greater than 1 is either a prime number or a product of prime numbers.

Lets say that P (n) is true if n is a prime or a product of prime numbers. We want to show that P (n) is true for all n > 1.

The base case is n=2. P (2) is true because 2 is prime.

Now lets use the inductive hypothesis. Lets take a number n > 2, and we will assume that P (k) is true for any integer k such that 1 < k < n. We want to show that P (n) is true. We may assume that n is not prime, otherwise, P (n) would be trivially true. Since n is not prime, there exist positive integers a, b greater than 1 such that a*b = n. Note that 1 < a < n and 1 < b < n, thus P (a) and P (b) are true. Therefore there exists primes p1, ..., pj and pj+1, ..., pl such that

p1*p2 * ... * pj = a

pj+1*pj+2 * ... * pl = b

As a result

n = a*b = (p1 * ... * pj) * (pj+1 * ... * pl) = p1 * ... * pj * ... pl

Since we could write n as a product of primes, then P (n) is also true. For strong induction, we conclude than P (n) is true for all integers greater than 1.