1.2 Prime Factorization, HCF and LCM

1. Prime Factorization

Every composite number can be uniquely expressed as a product of prime numbers. This is called the Fundamental Theorem of Arithmetic.

1
Divide the number by the smallest possible prime (2, 3, 5...).
2
Continue dividing the result until you reach 1 or a prime number.
3
Write the result in index notation (e.g., $2^{3}$ ).

Tip: Always check if the number is even (divisible by 2) or ends in 5 (divisible by 5) or sum of digits is divisible by 3.

Example: Factor Tree for 60

QWorked Examples: Prime Factorization

Consider the number 168.

(a) Use a factor tree or division method to find the prime factors of 168.

(b) Write 168 as a product of its prime factors in index notation.

168 \times k

is a perfect square, find the smallest positive integer value of

k

(a) Factor Tree:

Primes are: 2, 2, 2, 3, 7.

(b) Index Notation:

168 = 2 \times 2 \times 2 \times 3 \times 7

= 2^{3} \times 3 \times 7

(c) Perfect Square:

For a number to be a perfect square, all prime factors must have even powers.

Current powers:

2^{3}, 3^{1}, 7^{1}

To make powers even, we need one more 2 (to make

2^{4}

), one more 3 (to make

3^{2}

), and one more 7 (to make

7^{2}

k = 2 \times 3 \times 7 = 42

Check:

168 \times 42 = 7056

, and

\sqrt{7056} = 84

(a) Express 504 using prime factorization.

(b) Find the smallest integer

n

such that

\frac{504}{n}

is a perfect cube.

\sqrt[3]{\frac{504}{n}}

(a) Prime Factorization of 504:

504 = 2^{3} \times 3^{2} \times 7

(b) Perfect Cube Division:

For a perfect cube, all indices must be multiples of 3.

Indicies:

2^{3}

(multiple of 3, OK),

3^{2}

(extra 2),

7^{1}

(extra 1).

To leave only multiples of 3, we must divide by the "extras".

Remove

3^{2}

and

7^{1}

n = 3^{2} \times 7 = 9 \times 7 = 63

(c) Calculate Root:

\frac{504}{63} = 8

\sqrt[3]{8} = 2

The number

A = 2^{3} \times 3^{x} \times 5

and the number

B = 2^{y} \times 3^{2} \times 7

The Highest Common Factor (HCF) of A and B is

2^{2} \times 3

The Lowest Common Multiple (LCM) of A and B is

2^{3} \times 3^{2} \times 5 \times 7

(a) Find the values of

x

and

y

(b) Calculate the value of

A

(a) Find x and y:

HCF Rule: Lowest power of common bases.

Comparing

2^{3}

and

2^{y}

: HCF has

2^{2}

. So smallest power is 2. Thus

y = 2

Comparing

3^{x}

and

3^{2}

: HCF has

3^{1}

. So smallest power is 1. Thus

x = 1

Check LCM: Highest power.

2^{3}, 2^{2} \to 2^{3}

(Correct).

3^{1}, 3^{2} \to 3^{2}

(Correct).

Answer:

x = 1, y = 2

(b) Value of A:

A = 2^{3} \times 3^{1} \times 5

= 8 \times 3 \times 5 = 24 \times 5 = 120

Write 198 and 210 as products of their prime factors. Hence, or otherwise:

(a) Find the greatest integer that divides both 198 and 210.

(b) Find the smallest integer that is a multiple of both 198 and 210.

198 \times 210

is a perfect square. Explain.

Prime Factorization:

198 = 2 \times 99 = 2 \times 9 \times 11 = 2 \times 3^{2} \times 11

210 = 10 \times 21 = 2 \times 5 \times 3 \times 7 = 2 \times 3 \times 5 \times 7

(a) Greatest Divisor (HCF):

Common factors:

2^{1}

and

3^{1}

H C F = 2 \times 3 = 6

(b) Smallest Multiple (LCM):

Max powers:

2^{1}, 3^{2}, 5^{1}, 7^{1}, 11^{1}

L C M = 2 \times 9 \times 5 \times 7 \times 11

= 90 \times 77 = 6930

(c) Product Square?

P = (2 \times 3^{2} \times 11) \times (2 \times 3 \times 5 \times 7)

Combine powers:

2^{2} \times 3^{3} \times 5^{1} \times 7^{1} \times 11^{1}

Not all powers are even (3, 5, 7, 11 have odd powers). So No.

(a) List the factors of 45.

(b) List the prime factors of 45.

(d) Is 45 a prime number? Explain.

(a) Factors: Pairs that multiply to 45.

1, 3, 5, 9, 15, 45.

(b) Prime Factors:

From the list above, only 3 and 5 are prime.

(c) Prime Factorization:

45 = 3 \times 15 = 3 \times 3 \times 5 = 3^{2} \times 5

(d) Is it Prime?

No, it has factors other than 1 and itself (e.g., 5).

Using prime factorization only (do not use a calculator), evaluate:

\sqrt{1764}

Show your working clearly.

Factorize 1764:

1764 \div 2 = 882

882 \div 2 = 441

441 \div 3 = 147

(sum of digits 9, div by 3).

147 \div 3 = 49

49 \div 7 = 7

1764 = 2^{2} \times 3^{2} \times 7^{2}

Take square root:

\sqrt{1764} = \sqrt{2^{2} \times 3^{2} \times 7^{2}}

Halve the indices:

= 2^{1} \times 3^{1} \times 7^{1}

= 2 \times 3 \times 7 = 42

Given that

504 = 2^{3} \times 3^{2} \times 7

Find the value of

\sqrt{504 \times 14}

504 \times 14 = (2^{3} \times 3^{2} \times 7) \times (2 \times 7)

Combine indices:

= 2^{4} \times 3^{2} \times 7^{2}

Square root means halving the powers:

= 2^{2} \times 3^{1} \times 7^{1}

= 4 \times 3 \times 7 = 84

Write 360 as a product of its prime factors using a factor tree.

Give your answer in index notation.

360 = 10 \times 36

10 = 2 \times 5

36 = 6 \times 6 = (2 \times 3) \times (2 \times 3) = 2^{2} \times 3^{2}

Combine:

360 = 2 \times 5 \times 2^{2} \times 3^{2}

= 2^{3} \times 3^{2} \times 5

Given numbers

A = 2^{5} \times 3^{4} \times 5^{3}

Find the smallest positive integer

k

such that

A \times k

is a perfect cube.

For a perfect cube, indices must be multiples of 3.

Current indices:

2^{5}

: needs

2^{1}

more to become

2^{6}

3^{4}

: needs

3^{2}

more to become

3^{6}

5^{3}

: already multiple of 3 (OK).

k = 2^{1} \times 3^{2}

k = 2 \times 9 = 18

10.

Two numbers

A

and

B

are given by:

A = 2^{x} \times 3^{2}

B = 2^{3} \times 3^{y}

Their Highest Common Factor (HCF) is

2^{2} \times 3

Find the values of

x

and

y

HCF takes the lowest power of common factors.

For base 2: Comparing

2^{x}

and

2^{3}

The HCF has

2^{2}

. So the lower power is 2. Thus

x = 2

For base 3: Comparing

3^{2}

and

3^{y}

The HCF has

3^{1}

(which is 3). So the lower power is 1. Thus

y = 1

Answer:

x = 2, y = 1

11.

Evaluate

\sqrt[3]{2^{9} \times 3^{6}}

without using a calculator.

Cube root means dividing the indices by 3.

(2^{9} \times 3^{6})^{1 / 3} = 2^{9 \div 3} \times 3^{6 \div 3}

= 2^{3} \times 3^{2}

= 8 \times 9 = 72

12.

A gardener has 216 plants. He wants to plant them in rectangular rows.

The number of rows is a prime number.

The number of plants in each row is a multiple of 8.

Find the number of rows and the number of plants per row.

Area

= 216

. Factors of 216:

216 = 6^{3} = 2^{3} \times 3^{3}

Number of rows (

R

) is prime. Possible primes from factors: 2, 3.

Number of plants per row (

C

) is multiple of 8.

Case 1:

R = 2

C = 216 / 2 = 108

. Is 108 divisible by 8?

108 = 8 \times 13.5

(No).

Case 2:

R = 3

C = 216 / 3 = 72

. Is 72 divisible by 8?

72 = 8 \times 9

(Yes).

Answer: 3 rows, 72 plants per row.

2. HCF and LCM

Using prime factorization is the most reliable method for larger numbers.

Highest Common Factor (HCF)

The largest number that divides both numbers exactly.

Rule: Take the LOWEST power of common prime factors.

Lowest Common Multiple (LCM)

The smallest number that is a multiple of both numbers.

Rule: Take the HIGHEST power of ALL prime factors involved.

Venn Diagram Method

QWorked Examples: HCF and LCM

Find the Highest Common Factor (HCF) and Lowest Common Multiple (LCM) of 60 and 72.

(a) HCF

(b) LCM

H C F \times L C M = P r o d u c t o f N u m b e r s

60 = 2^{2} \times 3 \times 5

72 = 2^{3} \times 3^{2}

(a) HCF:

Lowest powers:

2^{2}

and

3^{1}

4 \times 3 = 12

(b) LCM:

Highest powers:

2^{3} \times 3^{2} \times 5

8 \times 9 \times 5 = 360

(c) Verification:

12 \times 360 = 4320

60 \times 72 = 4320

They match.

Two lights flash at different intervals.

Light A flashes every 12 seconds.

Light B flashes every 18 seconds.

They flash together at 10:00:00.

(a) Find the time interval (in seconds) until they next flash together.

(b) At what time exactly will they flash together next?

(a) Find LCM:

12, 24, 36, 48...

18, 36, 54...

LCM is 36 seconds.

(b) Next Time:

10:00:36.

(c) Frequency:

5 minutes =

5 \times 60 = 300

seconds.

300 \div 36 = 8.33

They clash on the 36th, 72nd... up to 288th second.

So 8 times.

A rectangular courtyard measures 840 cm by 720 cm.

Square tiles of the same size are to be used to cover the floor completely, without cutting any tiles.

(a) Find the largest possible side length of a square tile.

(b) Calculate the number of tiles needed.

This is an HCF problem (the side length must divide both dimensions).

(a) Determine HCF(840, 720):

840 = 10 \times 84 = 2 \times 5 \times 4 \times 21 = 2^{3} \times 3 \times 5 \times 7

720 = 10 \times 72 = 2 \times 5 \times 8 \times 9 = 2^{4} \times 3^{2} \times 5

Common:

2^{3}

3^{1}

5^{1}

H C F = 8 \times 3 \times 5 = 120

cm.

(b) Number of tiles:

Dimension 1:

840 \div 120 = 7

tiles.

Dimension 2:

720 \div 120 = 6

tiles.

Total Area / Tile Area =

7 \times 6 = 42

tiles.

Given numbers

P = 2^{a} \times 3^{b} \times 5^{c}

and

Q = 2^{3} \times 3^{2} \times 7

The HCF of P and Q is

12

The LCM of P and Q is

5040

(a) Express 12 and 5040 as products of prime factors.

(b) Find the values of

a, b, c

(a) Constants:

12 = 2^{2} \times 3

5040 = 504 \times 10

. From earlier Q,

504 = 2^{3} \times 3^{2} \times 7

5040 = 2^{3} \times 3^{2} \times 7 \times 2 \times 5 = 2^{4} \times 3^{2} \times 5 \times 7

(b) Logic:

For

2

: max is 4 (from LCM), min is 2 (from HCF). Q has

2^{3}

Since Q has

2^{3}

but LCM has

2^{4}

, P must provide the

2^{4}

. So

a = 4

For

3

: max is 2, min is 1. Q has

3^{2}

Since Q has

3^{2}

(the max), P must provide the min. So

b = 1

For

5

: LCM has

5

, Q has none. P must have

5^{1}

. So

c = 1

Answer:

a = 4, b = 1, c = 1

Complete the Venn Diagram method to find the HCF and LCM of 42 and 70.

(a) List prime factors of 42.

(b) List prime factors of 70.

(a) 42:

2 \times 3 \times 7

(b) 70:

2 \times 5 \times 7

(c) Venn Intersection: Common factors

2, 7

H C F = 2 \times 7 = 14

Venn Union: Intersection + Leftovers.

Leftover in 42: 3. Leftover in 70: 5.

L C M = (2 \times 7) \times 3 \times 5 = 14 \times 15 = 210

Three numbers are: 12, 18, and

x

Their HCF is 6 and their LCM is 180.

Find the smallest possible value for

x

Analyze Primes:

12 = 2^{2} \times 3

18 = 2 \times 3^{2}

H C F = 6 = 2 \times 3

L C M = 180 = 18 \times 10 = 2^{2} \times 3^{2} \times 5

Deduce x:

LCM power of 2 is

2^{2}

. (12 has

2^{2}

, so x doesn't need higher than

2^{1}

necessarily, but must satisfy HCF).

HCF has

2^{1}

. 12 contributes

2^{2}

, 18 contributes

2^{1}

. So x must have at least

2^{1}

LCM power of 3 is

3^{2}

. (18 has

3^{2}

HCF has

3^{1}

. 12 contributes

3^{1}

. So x must have at least

3^{1}

LCM has

5^{1}

. Neither 12 nor 18 have 5. So

x

MUST have

5^{1}

For x to be smallest, we take minimum powers needed for HCF.

x

must have factor

6

(HCF) and the missing

5

Try

x = 2^{1} \times 3^{1} \times 5 = 30

Check: HCF(12,18,30): common is

2 \times 3 = 6

. (Correct)

Check: LCM(12,18,30):

2^{2}, 3^{2}, 5^{1} \to 4 \times 9 \times 5 = 180

. (Correct)

Answer: 30.

Three bells toll at intervals of 12, 15, and 20 minutes respectively.

They start tolling together at 9:00 AM.

When will they next toll together?

Find LCM of 12, 15, 20.

12 = 2^{2} \times 3

15 = 3 \times 5

20 = 2^{2} \times 5

LCM

= 2^{2} \times 3 \times 5 = 4 \times 3 \times 5 = 60

minutes.

60 minutes = 1 hour.

9 : 00 + 1 : 00 = 10 : 00

AM.

Bus A departs every 24 minutes.

Bus B departs every 30 minutes.

Bus C departs every 45 minutes.

If they all depart together at 08:00, at what time will they next depart together?

Find LCM of 24, 30, 45.

24 = 2^{3} \times 3

30 = 2 \times 3 \times 5

45 = 3^{2} \times 5

LCM

= 2^{3} \times 3^{2} \times 5

= 8 \times 9 \times 5 = 72 \times 5 = 360

minutes.

360 \div 60 = 6

hours.

08:00 + 6 hours = 14:00 (or 2:00 PM).

Find the smallest number that leaves a remainder of 1 when divided by 6, 8, and 9.

First, find the LCM of 6, 8, and 9.

6 = 2 \times 3

8 = 2^{3}

9 = 3^{2}

LCM

= 2^{3} \times 3^{2} = 8 \times 9 = 72

The number is one more than a multiple of the LCM.

N u m b e r = 72 + 1 = 73

10.

Given

x = 2^{5} \times 3^{4}

and

y = 2^{3} \times 3^{6}

(a) Find the HCF in index notation.

(b) Find the LCM in index notation.

(a) HCF:

Take lowest powers:

2^{3}

and

3^{4}

HCF

= 2^{3} \times 3^{4}

(b) LCM:

Take highest powers:

2^{5}

and

3^{6}

LCM

= 2^{5} \times 3^{6}

11.

The product of two numbers is 300.

Their HCF is 5.

Find their LCM.

Using the rule:

H C F \times L C M = P r o d u c t

5 \times L C M = 300

L C M = 300 \div 5

L C M = 60

12.

A floor measures 4.8 m by 3.2 m.

It is to be covered with square tiles of side length

x

cm.

Find the largest possible integer value of

x

and the total number of tiles.

Convert to cm: 480 cm by 320 cm.

Largest tile size = HCF(480, 320).

480 = 10 \times 48 = 10 \times 16 \times 3 = 160 \times 3

320 = 10 \times 32 = 10 \times 16 \times 2 = 160 \times 2

Common factor is 160.

x = 160 cm.

Number of tiles:

(480 / 160) \times (320 / 160) = 3 \times 2 = 6

tiles.