HCF & LCM using Prime Factorization

We use prime factorization, that's writing a number as a product of its prime factors, to find two (or more) numbers' Highest Common Factor (HCF) and Least Common Multiple (LCM).

This is particularly useful when trying to find the HCF, or LCM, of large numbers.

Tutorial

To see the lesson notes, written in class, click on the button below.

Lesson Notes

Method for Finding the Highest Common Factor (HCF)

Given two numbers, such as $$36$$ and $$120$$ we can find their Highest Common Factor, HCF, written $HCF\begin{pmatrix}36,120\end{pmatrix}$ in two steps:

• Step 1: write both whole numbers as products of their prime factors.
For $$36$$ and $$120$$ that would be: $36 = 2^2 \times 3^2$
and
$120 = 2^3 \times 3 \times 5$
• Step 2: The HCF equals to the product of the prime factors both numbers have in common, each of which is raised to the lowest power seen.
For $$36$$ and $$120$$, the prime factors they have in common are: $2 \quad \text{and} \quad 3$ The lowest power of $$2$$ is $$2^2$$, the lowest power of $$3$$ is $$3$$. So the highest common factor, HCF, is: $HCF(36,120) = 2^2\times 3$

Method for Finding the Least Common Multiple (LCM)

Given two numbers, such as $$36$$ and $$120$$ we can find their Least Common Multiple, LCM, written $LCM\begin{pmatrix}36,120\end{pmatrix}$ in two steps:

• Step 1: write both whole numbers as products of their prime factors.
For $$36$$ and $$120$$ that would be: $36 = 2^2 \times 3^2$
and
$120 = 2^3 \times 3 \times 5$

• Step 2: The LCM equals to the product of all the distinct (different) prime factors seen, each of which is raised to the highest power seen.
For $$36$$ and $$120$$, the prime factors seen are: $2, \ 3, \ 5$ The highest power of $$2$$ is $$2^3$$, the highest power of $$3$$ is $$3^2$$ and the highest power of $$5$$ is $$5$$. So the least common multiple, LCM, is: $LCM(36,120) = 2^3\times 3^2\times 5$

Exercise 1

Leaving your answers as products of prime factors, find the Highest Common Factor, HCF, and the Least Common Multiple, LCM, of each of the following pairs of whole numbers:

1. $$75$$ and $$20$$
2. $$90$$ and $$84$$
3. $$36$$ and $$60$$
4. $$225$$ and $$135$$
5. $$100$$ and $$150$$
6. $$180$$ and $$126$$
7. $$324$$ and $$144$$
8. $$495$$ and $$525$$

Note: this exercise can be downloaded as a worksheet to practice with:

1. $$HCF = 5$$ and $$LCM = 2^2\times 3 \times 5^2$$
2. $$HCF(90,84) = 2\times 3$$ and $$LCM(90,84) = 2^2 \times 3^2 \times 5 \times 7$$
3. $$HCF(36,60) = 2^2 \times 3$$ and $$LCM(36,60) = 2^2 \times 3^2 \times 5$$.
4. $$HCF(225,135) = 3^2 \times 5$$ and $$LCM(225,135) = 3^3 \times 5^2$$
5. $$HCF(100,150) = 2\times 5^2$$ and $$LCM(100,150) = 2^2 \times 3\times 5^2$$
6. $$HCF(180,126) = 2\times 3^2$$ and $$LCM(180,126)=2^2 \times 3^2 \times 5 \times 7$$
7. $$HCF(324,144) = 2^2\times 3^2$$ and $$LCM(324,144) = 2^4\times 3^4$$
8. $$HCF(495,525) = 3\times 5$$ and $$LCM(495,525) = 3^2\times 5^2 \times 7 \times 11$$