HCF and LCM: Prime Factorisation and Word Problems

Two Everyday Questions

Three church bells ring every 12, 15 and 20 minutes. If they ring together at 8:00 am, when will they next ring together? A room is 4.8 m by 3.6 m. What is the largest square tile that will cover the floor exactly without cutting? The first question needs the lowest common multiple, and the second needs the highest common factor. This tutorial covers HCF and LCM for BECE, WAEC, NECO and JAMB mathematics: factors, multiples and prime numbers, prime factorisation using index notation, three methods of finding HCF and LCM, the link HCF × LCM = product of the numbers, and word problems on bells, tiles, sharing and remainders, with worked examples.

Factors, Multiples and Prime Numbers

A factor of a number divides it exactly. The factors of 12 are 1, 2, 3, 4, 6 and 12.
A multiple of a number is the result of multiplying it by a whole number. The multiples of 12 are 12, 24, 36, 48, …
A prime number has exactly two factors: 1 and itself. The first primes are 2, 3, 5, 7, 11, 13, 17, 19, 23 and 29. Note that 1 is not prime, and 2 is the only even prime.
A common factor of two numbers divides both, and a common multiple is a multiple of both.

The highest common factor (HCF), also called the greatest common divisor (GCD), is the largest number that divides all the given numbers exactly. The lowest common multiple (LCM) is the smallest number that all the given numbers divide into exactly.

Prime Factorisation

Every whole number greater than 1 can be written as a product of primes in exactly one way. To find it, divide repeatedly by primes, starting with the smallest.

Worked example 1

Express 360 as a product of prime factors in index form.

360 ÷ 2 = 180, 180 ÷ 2 = 90, 90 ÷ 2 = 45, 45 ÷ 3 = 15, 15 ÷ 3 = 5, 5 ÷ 5 = 1.

So 360 = 2 × 2 × 2 × 3 × 3 × 5 = 2³ × 3² × 5.

This repeated division is often set out as a "ladder" or "division table", with the primes down the left side.

Method 1: HCF and LCM by Listing

For small numbers, list the factors or multiples.

Factors of 18: 1, 2, 3, 6, 9, 18. Factors of 24: 1, 2, 3, 4, 6, 8, 12, 24. The common factors are 1, 2, 3 and 6, so the HCF is 6.

Multiples of 18: 18, 36, 54, 72, 90, … Multiples of 24: 24, 48, 72, 96, … The first common multiple is 72, so the LCM is 72.

Listing becomes slow for larger numbers, so the prime factor method is preferred.

Method 2: HCF and LCM by Prime Factors

Write each number in prime factor (index) form. Then:

HCF: take only the primes common to all the numbers, each with its lowest power.
LCM: take every prime that appears in any of the numbers, each with its highest power.

Worked example 2

Find the HCF and LCM of 84 and 120.

84 = 2² × 3 × 7 and 120 = 2³ × 3 × 5.

HCF: the common primes are 2 and 3. Lowest powers: 2² × 3 = 12.

LCM: all the primes 2, 3, 5 and 7, with highest powers: 2³ × 3 × 5 × 7 = 840.

Worked example 3

Find the HCF and the LCM of 36, 48 and 60.

36 = 2² × 3², 48 = 2⁴ × 3 and 60 = 2² × 3 × 5.

HCF = 2² × 3 = 12.

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

Method 3: The Euclidean Algorithm

For large numbers, the HCF can be found without factorising, using the fact that the HCF of two numbers also divides their difference and their remainder. Divide the larger number by the smaller, then divide the smaller number by the remainder, and repeat until the remainder is zero. The last non-zero remainder is the HCF.

Worked example 4

Find the HCF of 252 and 198.

252 = 1 × 198 + 54

198 = 3 × 54 + 36

54 = 1 × 36 + 18

36 = 2 × 18 + 0

The last non-zero remainder is 18, so HCF = 18. This 2,300-year-old method is also how computers find HCFs, as explained in the tutorial on number theory algorithms.

The Link Between HCF and LCM

For any two numbers a and b:

HCF × LCM = a × b

Check with 84 and 120: 12 × 840 = 10,080, and 84 × 120 = 10,080. (This rule does not work for three or more numbers.)

Worked example 5

The HCF of two numbers is 6 and their LCM is 180. If one number is 36, find the other.

Other number = (6 × 180) ÷ 36 = 30.

Word Problems on HCF and LCM

The key is deciding which one the question needs:

LCM: events that repeat and happen "together again", or the "smallest number" that several numbers divide into. The answer is larger than the given numbers.
HCF: splitting things into the "largest" equal groups, pieces or tiles. The answer is smaller than the given numbers.

Worked example 6: bells

Three bells ring every 12, 15 and 20 minutes. They ring together at 8:00 am. When will they next ring together?

12 = 2² × 3, 15 = 3 × 5 and 20 = 2² × 5. LCM = 2² × 3 × 5 = 60 minutes.

They ring together again at 9:00 am.

Worked example 7: tiles

A floor measures 4.8 m by 3.6 m. Find the largest square tile that will cover it exactly, and how many tiles are needed.

Work in centimetres: HCF(480, 360). 480 = 2⁵ × 3 × 5 and 360 = 2³ × 3² × 5, so HCF = 2³ × 3 × 5 = 120.

The largest tile is 120 cm by 120 cm. The floor holds 480 ÷ 120 = 4 tiles along one side and 360 ÷ 120 = 3 along the other, so 12 tiles are needed.

Worked example 8: sharing equally

A trader has 72 oranges and 96 mangoes. She wants to pack them into identical bags, with no fruit left over, using as many bags as possible. How many bags, and what goes in each?

HCF(72, 96) = 24, so she makes 24 bags, each containing 72 ÷ 24 = 3 oranges and 96 ÷ 24 = 4 mangoes.

Worked example 9: remainders

Find the smallest number which, when divided by 6, 8 or 12, leaves a remainder of 5 each time.

LCM(6, 8, 12) = 24 is divisible by all three. Adding 5 gives the required remainder: 29.

Worked example 10: perfect squares

Find the smallest whole number by which 72 must be multiplied to give a perfect square.

72 = 2³ × 3². A perfect square has every prime raised to an even power. The power of 2 is odd, so multiply by 2: 72 × 2 = 144 = 2⁴ × 3² = 12². The answer is 2.

Common Mistakes with HCF and LCM

Mixing up the rules: HCF uses the lowest powers of common primes; LCM uses the highest powers of all primes.
Using the wrong one in word problems. Ask whether the answer should be bigger or smaller than the numbers given.
Including 1 as a prime or forgetting that 2 is prime.
Applying HCF × LCM = a × b to three numbers. It only works for two.
Mixing units in measurement problems. Convert metres to centimetres first.

HCF and LCM: Practice Questions

Express 252 as a product of prime factors in index form.
Find the HCF and LCM of 54 and 90.
Find the highest common factor and lowest common multiple of 24, 36 and 60.
Three traffic lights change every 40 s, 60 s and 90 s. They change together at noon. After how many minutes do they next change together?
Find the largest number that divides 150 and 225 exactly.
Use the Euclidean algorithm to find the HCF of 391 and 299.

Answers: 1. 2² × 3² × 7. 2. 54 = 2 × 3³ and 90 = 2 × 3² × 5, so HCF = 18 and LCM = 270. 3. HCF = 12, LCM = 360. 4. LCM = 360 s = 6 minutes. 5. HCF = 75. 6. 391 = 1 × 299 + 92, 299 = 3 × 92 + 23, 92 = 4 × 23 + 0, so HCF = 23.

Conclusion

The HCF is the largest number that divides all the given numbers, and the LCM is the smallest number they all divide into. Prime factorisation makes both easy: the HCF uses the lowest powers of the common primes, and the LCM uses the highest powers of all the primes. For large numbers, the Euclidean algorithm finds the HCF quickly, and for two numbers HCF × LCM equals their product. In word problems, think "LCM for things that repeat together" and "HCF for the largest equal pieces".