Discrete Mathematics

----------------------------------------------P.ROOFMETHODSANDINDUCnON

23

Prime Factorization

Recall that a

prime

number is a

number

not evenly divisible

by

any

number

but

itself and one. 2, 3, 5, 7, 11,

... are primes. 4, 6, 8, 9,

10, 12, ... are not. They are composites.

Notice, however, that each composite can

be

broken

down

(factored) into primes.

For

example, 12 = 2 x 2 x 3. This

is

not

a coincidence.

Theorem

Every natural number

~

2

can

be written as the product

of

one

or

more primes.

I Proof I

We

use strong induction, where P(n) is the predicate

"n

can

be

written as the product

of

one

or

more

primes".

1111!1

'1:/n

~

2[P(n)]

1.

P(2) ...