Lesson 2 – Divisibility in the Set of Integers:

THE UNIQUE FACTORIZATION THEOREM

OBJECTIVES:
At the end of the lesson, the students will be able to:
 determine what is the Unique Factorization Theorem; and
 solve for the unique primes of a given numbers greater than 1.

INTRODUCTION:
Hello again students, hope you are still doing good! Welcome to another topic for
this lesson. In this part, you are about to learn about the Unique Factorization
Theorem and its Lemmas. So, are you ready? Alright, let’s begin!

ACTIVITY:
List down the prime factors of the following numbers.
1. 42
2. 72
3. 90
4. 150
5. 280
ANALYSIS:
 Students will explain the process of how they find the prime factors of
the given numbers.

ABSTRACTION:
Lesson 2 – Divisibility in the Set of Integers:
THE UNIQUE FACTORIZATION THEOREM

Unique Factorization Theorem

- also called “The Fundamental Theorem of Arithmetic”

7.1 Theorem (Fundamental Theorem of Arithmetic)

 Every number greater than 1 factor into a product of primes n = p1 p 2··· ps .
Further, writing the primes in ascending order p1 ≤ p2 ≤ ··· ≤ ps makes the
factorization unique.
Some of the primes in the product may be equal. For instance, 12 = 2·2·3 = 22
·3. So the Fundamental Theorem is sometimes stated as: every number greater than
1 can be factored uniquely as a product of powers of primes.

7.2 Example
1. 24 = 2·2·2·3 = 23·3
2. 160 = 2·4·4·5 = 2 · 4 2·5
3. 600 = 2·2·2·3·5·5 =23 ·3·52

7.3 Lemma (Euclid’s Lemma)

If p is a prime and p | ab, then p | a or p | b.
Proof. Assume that p | ab. If p | a then we are done, so suppose that it does not. Let
d = gcd(p,a) . Note that d > 0, and that d | p and d | a. Since d | p we have that d = 1
or d = p. If d = p then p | a, which we assumed was not true. So we must have d = 1.
Hence gcd(p,a) = 1 and p | ab. So by Lemma 5.6, (* 5.6 Lemma If a | bc and a is
relatively prime to b then a | c.) p | b.

For example:
If p = 19, a = 133, b = 143, then ab = 133 × 143 = 19019, and since this is
divisible by 19, the lemma implies that one or both of 133 or 143 must be as well. In
fact, 133 = 19 × 7.

7.4 Lemma
Let p be prime. Let a 1 a 2,..., a n, n ≥ 1, be integers. If p | a 1 a 2…a n, then p | a ifor
at least one i ∈ {1,2,...,n}.
PROOF. We use induction on n. For the n = 1 base case the result is clear. For the
inductive step, assume the inductive hypothesis: that the lemma holds for n such
that 1 ≤ n ≤ k. We must show that it holds for n = k + 1. Assume that p is prime and
that p | a 1 a 2···a k ak +1. Write a 1 a 2···a k as a, and a k+1 as b. Then p | a or p | b by
Lemma 7.3. If p | a = a 1···a k then by the induction hypothesis, p | a ifor some i ∈ {1,...,
k}. If p | b then p | a k+1. So we can say that p | a ifor some i ∈ {1, 2,…,k+1}. This
verifies the lemma for n = k +1. Hence by mathematical induction, it holds for all n
≥1.

7.5 Lemma (Existence)

If n > 1 then there exist primes, p1 . . . , ps , where s > 1 , such that n = p1 p2 . . .
ps and p1 < p2 < … < ps .

Proof: we will use induction on n. the base step is n = 2; in this case, since 2 is prime
we can take s = 1 and p1 = 2.
Assume the hypothesis that the lemma holds for 2 < n < k; shows that it holds for n =
k + 1. If k + 1 is prime then s = 1 and p1 = k + 1. If k + 1 is composite then write k + 1 =
ab where 1< a < k + 1 and 1< b < k + 1. By the induction hypothesis there are primes
p1, . . ., pu, and q1, . . . qv such that a = p1, . . ., pu and b = q1, . . ., qv. This gives that
k + 1 is a product of primes.

K + 1 = ab = p1p2 . . .puq1q2 . . .qv

Where s = u + v. Reorder the primes into ascending order, if necessary.
The base step and inductive step together give us that the statement is true for all n > 1.

For example: Consider the number 72.

The smallest prime number is 2, since 72 is even
72=2 ∙ 36
We can factor out more:
2
72=2 ∙ 2 ∙ 9
3
72=2 ∙ 3∙ 3
3 2
72=2 ∙ 3
 Rearrange the factors in any order
2 ∙2 ∙ 2∙ 3 ∙3
3 ∙3 ∙ 2 ∙2 ∙2
2 ∙3 ∙ 2∙ 3 ∙2
Rearranging the factors doesn’t cause a problem with uniqueness.

7.6 Lemma (Uniqueness)

If n = p1p2 . . . ps for s > 1 with p1< p2 < . . . < ps and also n = q1q2 . . .qt for
t > 1 with q1 < q2 < . . . < qt, then t = s, and pi = qi for all i between 1 and s.
Proof: the proof is by induction on s. In the s = 1 base case, n = p1 is prime and we
have p1 = q1q2 . . .qt. Now, t must be 1 or else this is factorization of prime p1, and
therefore p1 = q1.
Assume the inductive hypothesis that the result holds for all s with a < s < k. must
show that the result then holds for s = k + 1. Assume that n = p1p2, . . .pkpk+1 where p1
< p2 < . . . < p k + 1, and also n =q1q2, . . .qt where q1 < q2 < . . .< qt. Clearly pk+1 |n, so pk+1|
q1. . .qt. Euclid’s Lemma then give that pk+1 divides some qi. That implies that pk+1 = qi,
or else pk+1 would be non-1 divisor of the prime q1, which is impossible. Hence pk+1 =
qi < qt.

qt = pj < pk + 1. Therefore pk+1 = qt

k = t -1 and pi = qi for i = 1, . . ., t - 1
Lemma holds also in the s = k+1 case, so s > 1

7.7 Remark
Unique factorization gives an alternative, conceptually simpler way to find the
greatest common divisor of two numbers
(600, 252)
Get the prime factorization of each number
600 252
3 1 2 0 2 2 0
2 ∙3 ∙5 ∙ 7 2 ∙3 ∙5 ∙ 7
So gcd of (600, 252) = 22 ∙31 ∙5 0 ∙ 70= 24
APPLICATION:
Instruction: Find the unique prime factors of the following numbers.
1) 99
2) 32
3) 144
4) 160
5) 1, 092

ASSESSMENT:
I. Instruction: Find the unique prime factors of the following numbers.
1. 40
2. 800
3. 289
II. Instruction: Find the GCD of two numbers using unique prime factors.
1. (36, 54)
2. (420, 63)
3. (770, 900)
ANSWER KEY

ACTIVITY:

APPLICATION:
1. 99 = 3·3·11 = 32 ·11
2. 32= 2·2·2·2·2 = 25
3. 144= 2·2·2·2·3·3= 24 · 32
4. 160 = 2·4·4·5= 2 · 42 ·5
5. 1, 092 = 2·2·3·7·13= 22 ·3 · 7 ·13

ASSESSMENT:
I.
1. 40 = 2·2·2·5= 23 ·5
2. 800 = 2·2·2·2·2·5·5= 25 ·52
3. 289 = 17·17 = 172

II.
1. 36 54
2 ∙2 ∙ 3∙ 3 2 ∙3 ∙ 3 ∙3

GCD is 2 ∙3 ∙ 3=18

2. 420 63
2 2
2 ∙3 ∙ 5∙ 7 3 ∙7
GCD is 3 ∙7=21

3. 770 900
2 ∙5 ∙ 7 ∙11 2
2 ∙3 ∙5
2 2

GCD is 2 ∙5=10

REFERENCES
• Heffron, J. (2004). Elementary Number Theory. St Michael’s College. p15
• https://faculty.etsu.edu/gardnerr/3120/notes-Dudley/Dudley-Section-2.pdf
• https://en.wikipedia.org/wiki/Euclid%27s_lemma#:~:text=Euclid%27s
%20lemma%20%E2%80%94%20If%20a%20prime,143%20must%20be%20as
%20well
• https://www.expii.com/t/tfull-proof-of-fundamental-theorem-of-arithmetic-
3406