00-14 — Factors, Multiples, and Primes (Deep Dive)

Phase: 0 — Arithmetic & Number Foundations Subject: 00-14 Prerequisites: 00-01 — Whole Number Arithmetic, 00-08 — Basic Number Theory Next subject: 01-01 — Algebraic Expressions

Learning Objectives

By the end of this subject, you will be able to:

1. Construct factor trees and systematically derive the prime factorization of any composite number up to 1,000
2. Compute the Highest Common Factor (HCF) and Lowest Common Multiple (LCM) of three or more numbers using prime factorization
3. Solve real-world problems requiring HCF or LCM, including scheduling, packaging, and measurement problems
4. Use the Sieve of Eratosthenes to generate all primes up to 200 and explain why the method works
5. Test any number up to 1,000 for primality using the √n trial division method

Core Content

1. Review — What You Already Know

From Subject 00-01, you know: - A factor of n divides n exactly (no remainder). Factors come in pairs. - A multiple of n is n × k for some integer k. - A prime number has exactly two factors: 1 and itself. - Every composite number has a unique prime factorization (Fundamental Theorem of Arithmetic). - GCF (Greatest Common Factor, also called HCF — Highest Common Factor) is the largest number that divides two or more numbers. - LCM (Least Common Multiple) is the smallest number that is a multiple of two or more numbers.

From Subject 00-08, you know: - Divisibility rules for 2, 3, 4, 5, 6, 8, 9, 10, and 11. - The Euclidean algorithm for finding GCF of two numbers.

⚠️ THIS IS CRITICAL — This subject takes you deeper. You'll learn to handle three or more numbers at once, solve practical word problems, and confidently work with prime factorizations. These skills are essential for fractions, algebra (factoring polynomials), and advanced topics like cryptography and modular arithmetic.

2. Factor Trees — Systematic Prime Factorization

A factor tree breaks a number down into its prime factors by repeatedly splitting it into factor pairs.

Algorithm: 1. Write the number at the top 2. Find any two factors (not including 1 and itself — use the smallest prime factor for efficiency) 3. For each factor that is composite, repeat step 2 4. Stop when all branches end in prime numbers 5. Collect all primes to write the prime factorization

Example 1: Prime factorization of 180.

$          180
         /   \
        2     90
             /  \
            2   45
               /  \
              3   15
                 /  \
                3    5
$

Collect primes: 180 = 2 × 2 × 3 × 3 × 5 = 2² × 3² × 5

Systematic division method (more reliable for large numbers):

$180 ÷ 2 = 90
 90 ÷ 2 = 45
 45 ÷ 3 = 15
 15 ÷ 3 = 5
  5 ÷ 5 = 1
→ 180 = 2² × 3² × 5
$

Example 2: Prime factorization of 420.

$420 ÷ 2 = 210
210 ÷ 2 = 105
105 ÷ 3 = 35
 35 ÷ 5 = 7
  7 ÷ 7 = 1
→ 420 = 2² × 3 × 5 × 7
$

Example 3: Prime factorization of 693.

$Test 2: 693 is odd → no
Test 3: sum = 6+9+3 = 18, divisible by 3 → yes
693 ÷ 3 = 231
Test 3 again: 2+3+1 = 6, divisible by 3 → yes
231 ÷ 3 = 77
77 ÷ 7 = 11
11 ÷ 11 = 1
→ 693 = 3² × 7 × 11
$

⚠️ THIS IS CRITICAL — Always divide out ALL copies of each prime before moving to the next prime. For example, when factoring 180, divide by 2 twice (180→90→45) before moving to 3. Skipping a copy leads to incomplete factorization.

3. HCF (GCF) of Three or More Numbers

The Highest Common Factor of several numbers is the largest number that divides all of them.

Method using prime factorization: 1. Find the prime factorization of each number 2. Identify primes that appear in ALL factorizations 3. For each common prime, take the smallest (minimum) exponent 4. Multiply these together

Example 1: Find HCF(48, 72, 120).

$48 = 2⁴ × 3
72 = 2³ × 3²
120 = 2³ × 3 × 5

Common to ALL three: 2 and 3
Smallest exponent of 2: 3 (all have at least 2³)
Smallest exponent of 3: 1 (48 has 3¹, 72 has 3², 120 has 3¹)

HCF = 2³ × 3 = 8 × 3 = 24
$

Check: 48 ÷ 24 = 2 ✓, 72 ÷ 24 = 3 ✓, 120 ÷ 24 = 5 ✓

Example 2: Find HCF(60, 84, 150).

$60 = 2² × 3 × 5
84 = 2² × 3 × 7
150 = 2 × 3 × 5²

Common to ALL three: 2 and 3
Smallest 2 exponent: 1 (150 only has 2¹)
Smallest 3 exponent: 1 (all have 3¹)

HCF = 2 × 3 = 6
$

Check: 60 ÷ 6 = 10 ✓, 84 ÷ 6 = 14 ✓, 150 ÷ 6 = 25 ✓

What if there's no common prime? Then the HCF is 1 (the numbers are coprime or relatively prime).

Example 3: HCF(14, 33, 25). 14 = 2 × 7, 33 = 3 × 11, 25 = 5². No common primes → HCF = 1.

4. LCM of Three or More Numbers

The Lowest Common Multiple of several numbers is the smallest number that is a multiple of all of them.

Method using prime factorization: 1. Find the prime factorization of each number 2. Identify all primes that appear in ANY factorization 3. For each prime, take the largest (maximum) exponent 4. Multiply these together

Example 1: Find LCM(48, 72, 120).

48 = 2⁴ × 3
72 = 2³ × 3²
120 = 2³ × 3 × 5

All primes that appear: 2, 3, 5
Largest exponent of 2: 4 (from 48)
Largest exponent of 3: 2 (from 72)
Largest exponent of 5: 1 (from 120)

LCM = 2⁴ × 3² × 5 = 16 × 9 × 5 = 720

Check: 720 ÷ 48 = 15 ✓, 720 ÷ 72 = 10 ✓, 720 ÷ 120 = 6 ✓

Example 2: Find LCM(12, 18, 30).

12 = 2² × 3
18 = 2 × 3²
30 = 2 × 3 × 5

Primes: 2, 3, 5
Max 2: 2² (from 12)
Max 3: 3² (from 18)
Max 5: 5 (from 30)

LCM = 2² × 3² × 5 = 4 × 9 × 5 = 180

Check: 180 ÷ 12 = 15 ✓, 180 ÷ 18 = 10 ✓, 180 ÷ 30 = 6 ✓

5. HCF × LCM Relationship for More Than Two Numbers

For two numbers, we proved: HCF(a,b) × LCM(a,b) = a × b.

⚠️ THIS IS CRITICAL — This relationship does NOT extend simply to three or more numbers. For three numbers: HCF(a,b,c) × LCM(a,b,c) ≠ a × b × c.

Counterexample: Take 12, 18, 30. HCF = 6, LCM = 180. HCF × LCM = 6 × 180 = 1,080. But 12 × 18 × 30 = 6,480.

They're not equal! The two-number relationship is special and doesn't generalize.

6. The Sieve of Eratosthenes

The Sieve of Eratosthenes (named after the ancient Greek mathematician Eratosthenes, c. 276–194 BCE) is an ancient algorithm for finding all prime numbers up to a given limit.

Algorithm for finding all primes ≤ N:

1. Write down all numbers from 2 to N
2. Circle 2 (the first prime). Cross out all multiples of 2 (4, 6, 8, ...)
3. Find the next uncrossed number (3). Circle it. Cross out all its multiples (6, 9, 12, ... — some may already be crossed)
4. Find the next uncrossed number (5). Circle it. Cross out all its multiples
5. Repeat until you reach √N
6. All circled and remaining uncrossed numbers are prime

Why does it work? Any composite number ≤ N must have a prime factor ≤ √N. So by crossing out multiples of all primes up to √N, we eliminate all composites.

Example: Sieve for N = 30.

Initial: 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

Step 1 (circle 2, cross multiples): cross 4,6,8,10,12,14,16,18,20,22,24,26,28,30 Step 2 (circle 3, cross multiples): cross 9,15,21,27 (6,12,18,24,30 already crossed) Step 3 (circle 5, cross multiples): cross 25 (10,15,20,30 already crossed) Step 4: next uncrossed is 7. 7² = 49 > 30. Stop.

Primes ≤ 30: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29

We only needed to sieve with primes up to √30 ≈ 5.48 (so primes 2, 3, 5). After that, any composite ≤ 30 must have a factor ≤ 5.

7. Primality Testing — The √n Method

To determine whether a number n is prime:

1. Compute √n
2. Test divisibility by all primes ≤ √n
3. If none divide n evenly, n is prime

Why √n? If n is composite, it has a factor pair a × b = n. At least one of a or b must be ≤ √n (if both were > √n, their product would exceed n). So testing up to √n is sufficient.

Example 1: Is 97 prime? √97 ≈ 9.85. Test primes ≤ 9: 2, 3, 5, 7. - 97 ÷ 2 = 48.5 → not divisible - 97 ÷ 3 = 32.33 → not divisible (sum = 16, not divisible by 3) - 97 ÷ 5 → doesn't end in 0 or 5 → not divisible - 97 ÷ 7 = 13.857 → not divisible 97 is prime.

Example 2: Is 91 prime? √91 ≈ 9.54. Test primes ≤ 9: 2, 3, 5, 7. - 91 ÷ 2 → odd → no - 91 ÷ 3 → 9+1=10, not divisible by 3 → no - 91 ÷ 5 → doesn't end in 0 or 5 → no - 91 ÷ 7 = 13 → YES, 91 = 7 × 13 91 is composite.

Example 3: Is 323 prime? √323 ≈ 17.97. Test primes ≤ 17: 2, 3, 5, 7, 11, 13, 17. - 323 ÷ 2 → odd → no - 323 ÷ 3 → 3+2+3 = 8 → no - 323 ÷ 5 → no - 323 ÷ 7 = 46.14 → no - 323 ÷ 11 = 29.36 → no - 323 ÷ 13 = 24.85 → no - 323 ÷ 17 = 19 → YES, 323 = 17 × 19 323 is composite.

8. Real-World HCF/LCM Problems

HCF problems typically involve: dividing things into equal groups, finding the largest possible size of identical packages, or determining the maximum dimension that fits evenly.

LCM problems typically involve: finding when events will coincide again, determining the smallest quantity that can be packaged in different units, or synchronizing cycles.

Example 1 (HCF): You have 96 apples, 72 oranges, and 120 bananas. You want to make identical fruit baskets using all the fruit. What is the maximum number of identical baskets you can make, and what does each contain?

Find HCF(96, 72, 120):
96 = 2⁵ × 3
72 = 2³ × 3²
120 = 2³ × 3 × 5

HCF = 2³ × 3 = 24

Maximum baskets: 24
Each basket: 96÷24=4 apples, 72÷24=3 oranges, 120÷24=5 bananas

Example 2 (LCM): Three lighthouses flash at intervals of 6 seconds, 8 seconds, and 10 seconds. If they all flash together at midnight, when will they next flash together?

Find LCM(6, 8, 10):
6 = 2 × 3
8 = 2³
10 = 2 × 5

LCM = 2³ × 3 × 5 = 8 × 3 × 5 = 120

They'll flash together every 120 seconds = 2 minutes.
Next together: 12:02:00 AM.

Example 3 (HCF): A rectangular floor measures 540 cm by 420 cm. What is the side length of the largest square tile that can cover the floor exactly (no cutting)?

HCF(540, 420):
540 = 2² × 3³ × 5
420 = 2² × 3 × 5 × 7

HCF = 2² × 3 × 5 = 60

Largest square tile: 60 cm × 60 cm.
Number of tiles: 540÷60 = 9 tiles along length, 420÷60 = 7 tiles along width = 63 tiles total.

Worked Examples

Example 1: Prime Factorization with Factor Tree

Find the prime factorization of 504 by factor tree and systematic division.

Solution:

Factor tree:

$           504
          /   \
         2    252
             /   \
            2    126
                /   \
               2     63
                    /  \
                   3   21
                      /  \
                     3    7
$

Systematic division:

$504 ÷ 2 = 252
252 ÷ 2 = 126
126 ÷ 2 = 63
 63 ÷ 3 = 21
 21 ÷ 3 = 7
  7 ÷ 7 = 1
→ 504 = 2³ × 3² × 7
$

Answer: 504 = 2³ × 3² × 7

Example 2: HCF and LCM of Three Numbers

Find the HCF and LCM of 36, 54, and 90.

Solution:

Step 1 — Prime factorizations:

$36 = 2² × 3²
54 = 2 × 3³
90 = 2 × 3² × 5
$

Step 2 — HCF: Common primes in ALL: 2 and 3 Smallest exponent of 2: 1 (54 and 90 only have 2¹) Smallest exponent of 3: 2 (36 has 3², 54 has 3³, 90 has 3²)

HCF = 2¹ × 3² = 2 × 9 = 18

Step 3 — LCM: All primes: 2, 3, 5 Largest exponent of 2: 2 (from 36) Largest exponent of 3: 3 (from 54) Largest exponent of 5: 1 (from 90)

LCM = 2² × 3³ × 5 = 4 × 27 × 5 = 540

Step 4 — Verify: 36 ÷ 18 = 2 ✓, 54 ÷ 18 = 3 ✓, 90 ÷ 18 = 5 ✓ 540 ÷ 36 = 15 ✓, 540 ÷ 54 = 10 ✓, 540 ÷ 90 = 6 ✓

Example 3: Sieve of Eratosthenes up to 50

Use the Sieve to list all primes up to 50.

Solution:

Start: 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50

Sieve with 2: cross all even numbers ≥ 4 Remaining: 2, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 33, 35, 37, 39, 41, 43, 45, 47, 49

Sieve with 3: cross multiples of 3 (9, 15, 21, 27, 33, 39, 45) Remaining: 2, 3, 5, 7, 11, 13, 17, 19, 23, 25, 29, 31, 35, 37, 41, 43, 47, 49

Sieve with 5: cross multiples of 5 (25, 35) Remaining: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 49

Sieve with 7: cross multiples of 7 (49 — 7² = 49) Remaining: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47

√50 ≈ 7.07. No more primes to sieve with (next prime is 11, 11² = 121 > 50).

Primes up to 50: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47 (15 primes)

Example 4: Real-World LCM Problem

Three buses leave the depot at 6:00 AM. Bus A returns every 45 minutes, Bus B every 60 minutes, and Bus C every 75 minutes. When do all three buses next arrive at the depot together?

Solution:

Find LCM(45, 60, 75):

$45 = 3² × 5
60 = 2² × 3 × 5
75 = 3 × 5²

LCM = 2² × 3² × 5² = 4 × 9 × 25 = 900 minutes
$

900 minutes = 900 ÷ 60 = 15 hours.

Next together: 6:00 AM + 15 hours = 9:00 PM the same day.

Key Terms

• Example 3: Sieve Of Eratosthenes Up To 50
• Primality testing
• Correct: B) 7
• Why does it work?
• Answer: C) 97
• coprime
• Use the Sieve to list all primes up to 50.
• factor
• Review — What You Already Know
• What if there's no common prime?
• Factor Trees — Systematic Prime Factorization
• Example 2: Hcf And Lcm Of Three Numbers

Practice Problems

(Answers are below. Try each problem before checking.)

Problem 1: Find the prime factorization of 840.

Problem 2: Find the HCF and LCM of 24, 36, and 60.

Problem 3: Use the Sieve of Eratosthenes to find all primes between 1 and 40.

Problem 4: Is 203 prime? Use the √n method.

Problem 5: Three bells ring at intervals of 12, 18, and 30 minutes. If they all ring at noon, when do they next ring together?

Problem 6: A rectangular garden measures 96 m by 72 m. What is the largest square plot size that can divide the garden into equal square sections?

Problem 7: Find two numbers whose HCF is 8 and LCM is 480, given that one of the numbers is 80. What is the other number?

Summary

1. Prime factorization is the unique decomposition of any composite number into prime factors. Systematic division (dividing by primes in order) is the most reliable method.
2. HCF of 3+ numbers: find the prime factorization of each, then take common primes with the minimum exponent. LCM: take all primes with the maximum exponent.
3. The HCF × LCM = a × b relationship holds for exactly two numbers — it does NOT extend simply to three or more.
4. The Sieve of Eratosthenes efficiently finds all primes up to N by repeatedly crossing out multiples, stopping at √N.
5. Primality testing via trial division up to √n is sufficient because any composite n must have a factor ≤ √n.
6. HCF solves "grouping/splitting" problems (largest equal groups, largest tile size); LCM solves "synchronization" problems (next simultaneous event, common packaging size).

Pitfalls

• Forgetting to include ALL copies of a prime in the factorization. 12 = 2² × 3, not just 2 × 3 — you must count the multiplicity.
• Using the sum of numbers instead of product for the HCF/LCM relationship. HCF × LCM = a × b, NOT a + b.
• Applying the two-number HCF×LCM relationship to three numbers. It DOES NOT WORK for three or more numbers.
• Testing divisibility all the way up to n instead of √n for primality. For n = 97, you only need to test up to 9. The rest is wasted effort.
• Missing that 2 is the only even prime. When listing primes, don't accidentally include even numbers beyond 2.

Quiz

Answer each question, then read the explanation for your choice.

Q1: What is the prime factorization of 360?

A) 2² × 3² × 10 B) 2³ × 3² × 5 C) 2² × 3³ × 5 D) 2³ × 3 × 5²

Q2: Find the HCF of 28, 42, and 70.

A) 7 B) 14 C) 2 D) 28

Q3: Find the LCM of 12, 15, and 20.

A) 60 B) 30 C) 120 D) 300

Q4: When using the Sieve of Eratosthenes for N=100, up to which prime do you need to sieve?

A) 5 B) 7 C) 11 D) 13

Q5: Three cyclists ride around a track. Cyclist A takes 40 seconds per lap, B takes 55 seconds, and C takes 65 seconds. They start together. After how many seconds will they next cross the start line together?

A) 160 seconds B) 5,720 seconds C) 14,300 seconds D) 200 seconds

Q6: Is 221 prime?

A) Yes, it's prime B) No, 221 = 11 × 21 C) No, 221 = 13 × 17 D) No, 221 = 7 × 31

Q7: A rectangular floor is 480 cm by 360 cm. What is the side length of the largest square tile that will cover it exactly?

A) 120 cm B) 60 cm C) 80 cm D) 240 cm

Q8: For which of the following is the HCF × LCM = product of the numbers?

A) 12, 18, 24 B) 12 and 18 only C) 15, 20, 30 D) All of the above

Next Steps

Congratulations! You have completed Phase 0 — Arithmetic & Number Foundations.

Move on to Phase 1, Subject 01-01 — Algebraic Expressions to begin your study of algebra: variables, constants, substitution, like terms, expanding brackets, and factorising.

Q5: Three lighthouses flash every 8, 14, and 21 seconds. How often do they flash together?

A) Every 168 seconds B) Every 128 seconds C) Every 42 seconds D) Every 336 seconds

Answer: A) Every 168 seconds LCM(8, 14, 21): 8=2³, 14=2×7, 21=3×7. LCM = 2³×3×7 = 8×3×7 = 168.