Discrete Mathematics for Computer Science

68 CHAPTER 1 Sets, Proof Templates, and Induction

Inductive step

Base step no0 n0+1 n0+2 ni -

base

cases___________________ __

Assumed true cases

iStrong Form of Mathematical Induction )

Values for which the property is TRUE

Figure 1.18 Typical proof using the Strong Form of Induction.

Using Figure 1.18 as a guide, we now return to proving the result about factoring

integers. As noted above, the proof breaks into two cases: one case for prime numbers n,

and one case for nonprimes.

Theorem 1. (Part of the Fundamental Theorem of Arithmetic) Every natural num-

ber n such that n > 1 can be factored into a product of one or more primes.

Proof. The proof will use the Strong Form of Mathematical Induction. Let no = 2, and

let

T = {n E N : n > 1 and n = p1 • P2 " Pk for some prime numbers pl, P2, ... , Pk-

Let n be any natural number greater than or equal to 2.

(Base step) The base cases deal with any n that is a prime. Since n is prime, n = n is a

factorization of n into the product of one prime.

(Inductive step) In this step, we will prove the result for any n that is not a prime. As-

sume that for all m where 2 < m < n, m E T. Now, prove n E T.

Since n is not prime, n can be factored as n = k .m where k 0 1 and m : 1. It follows

easily that 1 < k < n and that 1 < m < n. Hence, by the inductive hypothesis, k, m E T.

So, k and m can be factored into products of primes:

k = pi • P2 ... Pi and m=q1•q2 .. •qj

Then,