Page 99 - 'Blast_Into_Math

Blast into Math! Prime nummers: indestructimle muilding mlocks

Theorem 5.2.1. (The Fundamental Theorem of Arithmetic (FTA)). Suppose n ∈ N and n> 1. Then

there exists a finite sequence of prime numbers

m
{p k } k=1

such that

m

n = p k .
k=1

These prime numbers are called the prime factors of n . This finite sequence of prime factors is unique up
to being re-arranged.

Proof: To prove the theorem, just like the chocolate chip proposition, we will use induction on the
number n . What is the base case? The first n ∈ N with n> 1 like the theorem states is n =2. In
that case, the set of prime factors of 2 is just {2}, because 2 is prime. So, the theorem is true when

n =2, and the unique finite sequence is

{2}.

To proceed by induction, we assume the theorem is true for all integers from 2 until some unknown

integer n ≥ 2. We need to then prove the theorem is true for n +1. If n +1 is a prime, then the
unique finite sequence of prime factors is {n +1} , and the theorem is true. If n +1 is not prime,
then by definition of prime, there is an integer x ∈ N which divides n +1 such that x =1 and
x = n +1. Since x ∈ N, and x =1,, we know that x> 1. By definition of divide,

n +1 = xy, y ∈ Z.

Since x> 0, and n +1 > 0, y> 0, so since y ∈ Z , it follows that y ∈ N . Since x> 1, we know
that y< n +1, because xy = n +1. Therefore,

1 <x<n +1, 1 <y <n +1.

By the induction assumption, the theorem is true for x and for y. This means that there are two finite
sequences of primes,

{p 1 ,p 2 ,...,p k } and {q 1 ,q 2 ,...,q m }

such that

x = p 1 ∗ p 2 ∗ ... ∗ p k and y = q 1 ∗ q 2 ∗ ... ∗ q m .

99