- Foundation
- About 14 min
- 5 practice questions
Finding the HCF using prime factorisation
Find the HCF of two or three numbers by taking each common prime the smallest number of times it appears, without listing all the factors.
If something looks wrong, please tell us.
By the end of this lesson you can
- Find the common factors of two numbers from their prime factorisations.
- Find the HCF by taking each common prime the minimum number of times.
- Find the HCF of three numbers, and recognise when the HCF is 1.
In the last lesson we saw that factors are sub-products of the primes. A common factor must therefore be a sub-product of both factorisations. The HCF is simply the biggest such shared piece, and we can build it directly.
Common factors from prime factorisations
Take 60 = 2 × 2 × 3 × 5 and 84 = 2 × 2 × 3 × 7. A common factor may only use primes found in both, and no more copies than either has. The shared part is 2 × 2 × 3. Its sub-products 1, 2, 3, 4, 6 and 12 are the common factors, and the biggest, 12, is the HCF. This matches what we found by listing in lesson 1.
To find the HCF, write each prime factorisation, take every prime that appears in all of them, use it the smallest number of times it appears in any one number, and multiply.
Worked example 1: HCF of 126 and 180
- 126 = 2 × 3 × 3 × 7 and 180 = 2 × 2 × 3 × 3 × 5.
- Common primes: 2 and 3. (7 is only in 126; 5 is only in 180.)
- 2 appears once in 126 and twice in 180, so take it once. 3 appears twice in each, so take it twice.
- HCF = 2 × 3 × 3 = 18. Check: 126 ÷ 18 = 7 and 180 ÷ 18 = 10, and 7 and 10 have no common factor except 1.
| Prime | Times in 126 | Times in 180 | Times in the HCF (minimum) |
|---|---|---|---|
| 2 | 1 | 2 | 1 |
| 3 | 2 | 2 | 2 |
| 5 | 0 | 1 | 0 |
| 7 | 1 | 0 | 0 |
Worked example 2: no common prime
Find the HCF of 64 and 135. Working: 64 = 2 × 2 × 2 × 2 × 2 × 2 and 135 = 3 × 3 × 3 × 5. No prime appears in both, so the only common factor is 1. HCF = 1: 64 and 135 are co-prime, even though neither is prime.
Worked example 3: three numbers
Find the HCF of 48, 72 and 120.
- 48 = 2 × 2 × 2 × 2 × 3; 72 = 2 × 2 × 2 × 3 × 3; 120 = 2 × 2 × 2 × 3 × 5.
- Primes in all three: 2 and 3.
- 2 appears 4, 3 and 3 times: minimum 3. 3 appears 1, 2 and 1 times: minimum 1.
- HCF = 2 × 2 × 2 × 3 = 24. Check: 48 ÷ 24 = 2, 72 ÷ 24 = 3, 120 ÷ 24 = 5.
HCF by prime factorisation
- Factorise Write each number as a product of primes.
- Find shared primes Keep only primes that appear in every number.
- Take the minimum Use each shared prime as few times as it appears in any number.
- Multiply The product is the HCF; if nothing is shared, the HCF is 1.
A common trap
Writing 72 = 6 × 12 and 144 = 8 × 18 and seeing no repeated number does not mean the numbers share no factor. Composite factors hide primes. Split fully: 72 = 2 × 2 × 2 × 3 × 3 and 144 = 2 × 2 × 2 × 2 × 3 × 3. The shared part is 2 × 2 × 2 × 3 × 3 = 72, so the HCF is 72 itself. Always go all the way down to primes.
Key takeaways: a common factor is a sub-product of every factorisation. The HCF uses each shared prime the minimum number of times. If no prime is shared, the HCF is 1. Never judge common factors from a split into composite numbers.
Check your understanding
-
1. Using prime factorisation, what is the HCF of 36 and 90?
- 6
- 9
- 18
- 180
Show answer
Answer: C. 36 = 2 × 2 × 3 × 3 and 90 = 2 × 3 × 3 × 5. Shared: one 2 and two 3s. HCF = 2 × 3 × 3 = 18.
-
2. What is the HCF of (2 × 2 × 3 × 5) and (2 × 3 × 3 × 7)?
- 6
- 2
- 3
- 1,260
Show answer
Answer: A. Shared primes: 2 (once in the second number) and 3 (once in the first). HCF = 2 × 3 = 6.
-
3. What is the HCF of 49 and 64?
- 7
- 1
- 8
- 4
Show answer
Answer: B. 49 = 7 × 7 and 64 = 2 × 2 × 2 × 2 × 2 × 2. No prime is shared, so the HCF is 1.
-
4. What is the HCF of 56, 98 and 140?
- 7
- 28
- 2
- 14
Show answer
Answer: D. 56 = 2 × 2 × 2 × 7, 98 = 2 × 7 × 7, 140 = 2 × 2 × 5 × 7. Primes in all three: 2 (minimum once) and 7 (minimum once). HCF = 2 × 7 = 14.
-
5. Ravi writes 72 = 6 × 12 and 144 = 8 × 18 and says the numbers have no common factor except 1. What is wrong?
- Nothing; he is right
- He should have used addition instead
- He stopped at composite numbers; in primes they share 2 × 2 × 2 × 3 × 3, so the HCF is 72
- 72 and 144 are both prime
Show answer
Answer: C. Composite factors hide primes. 72 = 2 × 2 × 2 × 3 × 3 and 144 = 2 × 2 × 2 × 2 × 3 × 3, so the shared part is 72, and 72 divides 144 exactly.
Sign in to keep track of the lessons you finish.