Highest Common Factor

Finding the highest common factor (HCF) of two or three numbers by prime factorisation, and using it in word problems.

Before you start

A factor of a number divides it exactly: the factors of 12 are 1, 2, 3, 4, 6 and 12.

A number can be written as a product of its prime factors in index notation: $360 = 2^{3} \times 3^{2} \times 5$ .

Common Factors and the HCF

A number that is a factor of two or more numbers is a common factor of those numbers. The largest of the common factors is their highest common factor (HCF).

Example 1: Listing the factors

Find the HCF of 18 and 24.

Solution

Factors of 18: 1, 2, 3, 6, 9, 18

Factors of 24: 1, 2, 3, 4, 6, 8, 12, 24

The numbers in both lists are the common factors: 1, 2, 3 and 6. The largest is 6.

The HCF of 18 and 24 is 6.

Definition

The highest common factor (HCF) of two or more numbers is the largest whole number that is a factor of every one of them.

Listing is slow for larger numbers, and a factor is easily missed. Prime factorisation is quicker.

HCF by Prime Factorisation

Every factor of a number is made from that number's prime factors. So a common factor can use only the primes that are in every number. It can use each of those primes only as many times as it appears in the number where it appears least often. For $36 = 2 \times 2 \times 3 \times 3$ and $120 = 2 \times 2 \times 2 \times 3 \times 5$ , that is two 2s and one 3.

Method

Write each number as a product of its prime factors in index notation.
Pick out the prime factors that are in all the numbers.
For each one, take its lowest power (the smallest index). A prime written with no index has index 1: $3 = 3^{1}$ .
Multiply these together.

The HCF is the product of the common prime factors, each with its lowest power.

Example 2: Two numbers

Find the HCF of 36 and 120.

Solution

Find each prime factorisation with a factor tree or by repeated division, as in the lesson on prime factorisation.

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

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

The common prime factors are 2 and 3. (5 is not a factor of 36, so it is left out.)

The lowest power of 2 is $2^{2}$ , from 36. The lowest power of 3 is $3$ , from 120, because $3 = 3^{1}$ and 1 is less than 2.

HCF $= 2^{2} \times 3 = 12$

The HCF of 36 and 120 is 12.

Example 3: Three numbers

Find the HCF of 84, 126 and 245.

Solution

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

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

$245 = 5 \times 7^{2}$

A table with a column for each prime shows what is common.

Prime factor	2	3	5	7
84	$2^{2}$	$3$	–	$7$
126	$2$	$3^{2}$	–	$7$
245	–	–	$5$	$7^{2}$
In all three (lowest power)	–	–	–	$7$

Only 7 is in all three numbers. (2 and 3 are in 84 and 126 but not in 245, so they are left out.) The lowest power of 7 is $7$ .

The HCF of 84, 126 and 245 is 7.

Example 4: Numbers in index notation

Find the HCF of $2^{3} \times 3^{2} \times 5$ , $2^{2} \times 3^{4} \times 5^{2}$ and $2^{4} \times 3^{3} \times 7$ , leaving your answer in index notation.

Solution

Only 2 and 3 are in all three numbers. (The third number has no 5, and the first two have no 7.)

The powers of 2 are $2^{3}$ , $2^{2}$ and $2^{4}$ . The lowest is $2^{2}$ .

The powers of 3 are $3^{2}$ , $3^{4}$ and $3^{3}$ . The lowest is $3^{2}$ .

The HCF is $2^{2} \times 3^{2}$ .

No common prime factor

$15 = 3 \times 5$ and $16 = 2^{4}$ have no common prime factor. Their only common factor is 1, so their HCF is 1 (not 0).

HCF by Repeated Division

We can also divide the numbers together. Write them in a row and divide all of them by a prime number that divides every one. Do the same with the quotients, until no prime number divides every number in the row.

Rule

The HCF is the product of the divisors on the left. If no prime number divides every number even at the start, there are no divisors and the HCF is 1.

Example 5: Repeated division

Use repeated division to find the HCF of 36 and 120.

Solution

2 divides both 36 and 120, giving 18 and 60.

2 divides both 18 and 60, giving 9 and 30.

3 divides both 9 and 30, giving 3 and 10.

No prime number divides both 3 and 10, so we stop.

HCF $= 2 \times 2 \times 3 = 12$

The HCF of 36 and 120 is 12, as in Example 2.

Word Problems

Use the HCF when the totals are given and they are put into equal groups or cut into equal parts with nothing left over, and the question asks for the greatest number of groups or the largest size. The answer must divide every quantity exactly, and the greatest number that does is the HCF.

Example 6: The greatest number of equal groups

A teacher packs 60 red markers and 84 blue markers into sets, using all of them. Every set has the same number of red markers, and every set has the same number of blue markers. What is the greatest number of sets she can make, and what is then in each set?

Solution

The number of sets must divide both 60 and 84 exactly. The greatest such number is their HCF.

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

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

HCF $= 2^{2} \times 3 = 12$

Each set has $60 \div 12 = 5$ red markers and $84 \div 12 = 7$ blue markers.

She can make at most 12 sets, each with 5 red markers and 7 blue markers.

Example 7: The largest square tile

A rectangular floor measuring 420 cm by 360 cm is to be covered with identical square tiles, with no tile cut.
(a) Find the length of the side of the largest tile that can be used.
(b) How many of these tiles are needed?

Solution

A whole number of tiles must fit along each side, so the side of a tile must divide both 420 cm and 360 cm exactly. The largest such length is given by the HCF of 420 and 360.

$420 = 2^{2} \times 3 \times 5 \times 7$

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

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

$420 \div 60 = 7$ tiles fit along the length and $360 \div 60 = 6$ along the breadth, so $7 \times 6 = 42$ tiles are needed.

(a) The side of the largest tile is 60 cm. (b) 42 tiles are needed.

Common Mistakes

Taking the highest power. For 36 and 120, $2^{3} \times 3^{2} = 72$ is not even a factor of 36. Take the lowest power of each common prime.
Keeping a prime that is not in every number. With three numbers, a prime in only two of them is left out.
Multiplying the last row in repeated division. Only the divisors on the left are multiplied.

Practice

Work each question on paper before you open its solution.

Question 1

List the factors of 28 and of 42. Write down their common factors and their HCF.

ShowHide solution

Factors of 28: 1, 2, 4, 7, 14, 28

Factors of 42: 1, 2, 3, 6, 7, 14, 21, 42

The common factors are 1, 2, 7 and 14. The HCF of 28 and 42 is 14.

Question 2

Find the HCF of 252 and 360 by prime factorisation.

ShowHide solution

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

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

The common prime factors are 2 and 3, with lowest powers $2^{2}$ and $3^{2}$ .

HCF $= 2^{2} \times 3^{2} = 4 \times 9 = 36$

The HCF of 252 and 360 is 36.

Question 3

Find the HCF of $3^{2} \times 5^{3} \times 7$ and $3^{4} \times 5 \times 7^{2}$ . Give your answer in index notation and as a number.

ShowHide solution

The primes 3, 5 and 7 are in both numbers. Their lowest powers are $3^{2}$ , $5$ and $7$ .

HCF $= 3^{2} \times 5 \times 7 = 9 \times 35 = 315$

The HCF is $3^{2} \times 5 \times 7$ , which is 315.

Question 4

Find the HCF of 80, 126 and 308.

ShowHide solution

$80 = 2^{4} \times 5$

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

$308 = 2^{2} \times 7 \times 11$

Only 2 is in all three numbers. (7 is in 126 and 308 but not in 80.) The lowest power of 2 is $2$ , from 126.

The HCF of 80, 126 and 308 is 2.

Question 5

Find the HCF of 35 and 72.

ShowHide solution

$35 = 5 \times 7$

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

There is no common prime factor, so the only common factor is 1.

The HCF of 35 and 72 is 1.

Question 6

Use repeated division to find the HCF of 36, 60 and 90.

ShowHide solution

2 divides all of 36, 60 and 90, giving 18, 30 and 45.

3 divides all of 18, 30 and 45, giving 6, 10 and 15.

No prime number divides all of 6, 10 and 15, so we stop, even though pairs of them still have a common prime factor.

HCF $= 2 \times 3 = 6$

The HCF of 36, 60 and 90 is 6.

Question 7

Mei Ling cuts two ribbons, 48 cm and 72 cm long, into pieces of equal length with no ribbon left over.
(a) What is the greatest possible length of each piece?
(b) How many pieces of this length does she get altogether?

ShowHide solution

The length of a piece must divide both 48 cm and 72 cm exactly, so the greatest length is given by their HCF.

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

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

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

The ribbons give $48 \div 24 = 2$ pieces and $72 \div 24 = 3$ pieces, and $2 + 3 = 5$ .

(a) The greatest possible length of each piece is 24 cm. (b) She gets 5 pieces altogether.

Question 8

A rectangular piece of cloth, 150 cm by 105 cm, is cut into identical squares with no cloth left over.
(a) Find the length of the side of the largest possible square.
(b) How many of these squares are there?

ShowHide solution

The side of a square must divide both 150 cm and 105 cm exactly, so the largest side is given by their HCF.

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

$105 = 3 \times 5 \times 7$

HCF $= 3 \times 5 = 15$

$150 \div 15 = 10$ squares fit along the length and $105 \div 15 = 7$ along the breadth, and $10 \times 7 = 70$ .

(a) The side of the largest square is 15 cm. (b) There are 70 squares.

Question 9

A class packs 90 pencils, 126 erasers and 198 stickers into goodie bags, using everything. Every bag has the same contents.
(a) What is the greatest number of goodie bags?
(b) With this number of bags, what is in each bag?

ShowHide solution

The number of bags must divide 90, 126 and 198 exactly, so the greatest number of bags is their HCF.

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

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

$198 = 2 \times 3^{2} \times 11$

HCF $= 2 \times 3^{2} = 18$

$90 \div 18 = 5$ , $126 \div 18 = 7$ and $198 \div 18 = 11$ .

(a) The greatest number of goodie bags is 18. (b) Each bag has 5 pencils, 7 erasers and 11 stickers.

Key Points

The highest common factor (HCF) of two or more numbers is the largest number that is a factor of every one of them.
By prime factorisation: multiply the prime factors common to all the numbers, each with its lowest power.
A prime factor missing from any one of the numbers is left out. With no common prime factor, the HCF is 1.
By repeated division: divide all the numbers by common prime factors until none is left, then multiply the divisors.
The greatest number of equal groups, or the largest equal size with nothing left over, is given by the HCF.