Question

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.

Answer 1

Answer:

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.