Number · Number Operations · Lesson 11

Finding the HCF Using Prime Factors in Index Form

How wide should you cut strips of cloth so that nothing is wasted? How many equal parcels can you make from two different heaps of oranges? These are Highest Common Factor (HCF) questions. In this lesson you will write numbers as products of prime powers and use them to find the HCF quickly, even for large numbers, and you will see how the same idea gives the LCM.

NaCCA B7.1.2.3.5 ⏱ about 50 min

By the end you will be able to

✔Write two or three numbers as products of prime factors in index form.
✔Find the HCF by multiplying the common primes, each with its lowest index.
✔Find the LCM by multiplying all the primes, each with its highest index.
✔Decide whether a word problem needs the HCF or the LCM, and solve it.

Key words

Common factor: A number that divides two or more numbers exactly. 3 is a common factor of 12 and 15.
Highest Common Factor (HCF): The largest number that divides each of the given numbers exactly. The HCF of 24 and 30 is 6.
Lowest Common Multiple (LCM): The smallest number that is a multiple of each of the given numbers. The LCM of 8 and 12 is 24.
Prime factorisation: Writing a number as a product of primes, e.g. 24 = $2^{3} \times 3$ .

Curriculum reference

Content standard: B7.1.2.3 Demonstrate understanding and the use of powers of natural numbers in solving problems.

Indicator: Apply the concept of powers of numbers (product of prime) to find Highest Common Factor (HCF).

Starter

Akweley's strips of paper

Akweley is making paper chains for her school's Independence Day decoration in Accra. She has one piece of coloured paper 24 cm wide and another 30 cm wide. She wants to cut both into strips of the same width, as wide as possible, with no paper wasted. Should the strips be 2 cm? 3 cm? 6 cm? Prime factors give the answer in a few lines.

1. Common factors and the HCF

A factor of a number divides it exactly. Listing factors is the method you learnt in primary school:

Factors of 24: 1, 2, 3, 4, 6, 8, 12, 24
Factors of 30: 1, 2, 3, 5, 6, 10, 15, 30
Common factors: 1, 2, 3, 6. The highest is 6, so HCF(24, 30) = 6.

Listing works for small numbers, but for numbers like 180 and 252 the lists become long and it is easy to miss a factor. Prime factors in index form give a faster, safer method.

▶ A strip width must divide BOTH widths exactly. The widest such width is the HCF.

2. The HCF from prime factors in index form

First write each number as a product of prime powers (use a factor tree or repeated division). Here is 24:

▶ Watch 24 break down to 2 × 2 × 2 × 3 = 2³ × 3.

Similarly, 30 = 2 × 3 × 5. Now line the numbers up prime by prime. A common factor can only use primes that appear in both numbers, and it cannot use more copies of a prime than the number with the fewest copies has. So for each common prime we take the lowest index.

HCF of 24 and 30
Number	Power of 2	Power of 3	Power of 5
24	$2^{3}$	$3^{1}$	— (none)
30	$2^{1}$	$3^{1}$	$5^{1}$
HCF (lowest index, common primes only)	$2^{1}$	$3^{1}$	not common

HCF = $2^{1} \times 3^{1}$ = 2 × 3 = 6, the same answer as listing. 5 is left out because 24 has no factor 5.

1Write each number as a product of prime factors in index form.
2Pick out the primes that appear in EVERY number.
3For each of those primes, take the LOWEST index.
4Multiply them together. That product is the HCF.

3. Bigger numbers and three numbers

The method shines for large numbers. 180 = $2^{2} \times 3^{2} \times 5$ and 252 = $2^{2} \times 3^{2} \times 7$ . Common primes: 2 and 3. Lowest indices: $2^{2}$ and $3^{2}$ . HCF = 4 × 9 = 36.

For three numbers, a prime must appear in all three. For 36, 54 and 90: 36 = $2^{2} \times 3^{2}$ , 54 = $2 \times 3^{3}$ , 90 = $2 \times 3^{2} \times 5$ . Common primes: 2 and 3. Lowest indices: $2^{1}$ and $3^{2}$ . HCF = 2 × 9 = 18.

4. HCF or LCM? Solving real problems

The LCM uses the same prime factors, but now we want the smallest number that every given number divides into. So we take every prime that appears, each with its highest index. For 12 = $2^{2} \times 3$ and 8 = $2^{3}$ : LCM = $2^{3} \times 3$ = 24.

Choosing the right tool
Clue in the question	Use	Why
Cut, share or pack into the largest equal groups/pieces	HCF	We divide each amount exactly (factor), into the same size (common), as big as possible (highest).
When will events happen together again? Smallest amount that can be shared equally both ways	LCM	The events repeat (multiples), must meet (common), as soon as possible (lowest).

Worked examples

Try each one yourself first, then open the solution and compare every step.

Example 1

HCF of 24 and 30

Use prime factors to find the HCF of 24 and 30.

Show the solution

Step 124 = 2 × 2 × 2 × 3 = $2^{3} \times 3$ .
Step 230 = 2 × 3 × 5.
Step 3Common primes: 2 and 3. Lowest indices: $2^{1}$ and $3^{1}$ .
Step 4HCF = 2 × 3 = 6.

Answer: HCF = 6

Example 2

HCF of 72 and 120

Find the HCF of 72 and 120, giving your answer in index form and as a number.

▶ The prime factors of 120: compare them with 72 = 2³ × 3² to see the common part.

Show the solution

Step 172 = $2^{3} \times 3^{2}$ (72 → 36 → 18 → 9 → 3 → 1).
Step 2120 = $2^{3} \times 3 \times 5$ (120 → 60 → 30 → 15 → 5 → 1).
Step 3Common primes: 2 and 3. Lowest index of 2 is 3; lowest index of 3 is 1.
Step 4HCF = $2^{3} \times 3$ = 8 × 3 = 24.
Step 5Check: 72 ÷ 24 = 3 and 120 ÷ 24 = 5; 3 and 5 share no factor ✓

Answer: HCF = $2^{3} \times 3$ = 24

Example 3

HCF of three numbers

Find the HCF of 36, 54 and 90.

Show the solution

Step 136 = $2^{2} \times 3^{2}$ .
Step 254 = $2 \times 3^{3}$ .
Step 390 = $2 \times 3^{2} \times 5$ .
Step 4Primes in all three: 2 and 3. Lowest indices: $2^{1}$ and $3^{2}$ .
Step 5HCF = 2 × 9 = 18.

Answer: HCF = 18

Example 4

Akweley's strips

Akweley has two pieces of paper, 24 cm and 30 cm wide. She wants to cut both into strips of equal width, as wide as possible, with nothing wasted. How wide should each strip be, and how many strips will she get altogether?

Show the solution

Step 1The width must divide 24 and 30 exactly and be as large as possible, so we need the HCF.
Step 224 = $2^{3} \times 3$ and 30 = 2 × 3 × 5, so HCF = 2 × 3 = 6 cm.
Step 3Strips: 24 ÷ 6 = 4 and 30 ÷ 6 = 5.
Step 4Altogether: 4 + 5 = 9 strips.

Answer: Each strip 6 cm wide; 9 strips altogether

Example 5

When will they meet again? (LCM)

Baba exercises every 12 days and Serwa every 8 days. Both exercised today. After how many days will they next exercise on the same day?

Show the solution

Step 1Repeating events meeting again → LCM.
Step 212 = $2^{2} \times 3$ and 8 = $2^{3}$ .
Step 3Take every prime with its highest index: $2^{3}$ and $3^{1}$ .
Step 4LCM = 8 × 3 = 24.

Answer: 24 days

Summary

Write each number as a product of prime factors in index form first.
HCF = product of the COMMON primes, each with its LOWEST index.
LCM = product of ALL the primes, each with its HIGHEST index.
The HCF divides every number, so it is never bigger than the smallest number.
Use HCF to cut/share into the largest equal parts; use LCM for events that repeat and meet again.

Akweley's strips of paper

1. Common factors and the HCF

2. The HCF from prime factors in index form

3. Bigger numbers and three numbers

4. HCF or LCM? Solving real problems

Worked examples

HCF of 24 and 30

HCF of 72 and 120

HCF of three numbers

Akweley's strips

When will they meet again? (LCM)

Summary

Practice: 15 questions