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 number 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, ... , PkLet 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. Assume 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,