How to find the highest common factor (HCF)
A factor of a number divides it exactly. A common factor divides two numbers. The highest common factor (HCF) is the biggest one. In the United States it is called the greatest common factor (GCF), and you may also see greatest common divisor (GCD). They all mean the same thing.
The rule
The highest common factor of two numbers is the biggest number that divides both of them exactly.
How to do it
- Write the two numbers side by side, and draw a line down their right-hand side.
- Find a prime that divides both numbers. Write it on the right of the line.
- Divide both numbers by it, and write the answers underneath.
- Keep going until no prime divides both. Multiply the primes on the right. That is the HCF.
Worked examples
What is the HCF of 12 and 18?
| 12 | 18 | 2 |
| 6 | 9 | 3 |
| 2 | 3 |
No prime divides both 2 and 3, so stop. HCF = 2 × 3 = 6.
What is the HCF of 120 and 180?
| 120 | 180 | 2 |
| 60 | 90 | 2 |
| 30 | 45 | 3 |
| 10 | 15 | 5 |
| 2 | 3 |
HCF = 2 × 2 × 3 × 5 = 60.
What is the HCF of 8 and 15?
2 divides 8, but not 15. 3 and 5 divide 15, but not 8.
No prime divides both, so the HCF is 1. Numbers like these are called coprime.
Another way, for small numbers
List every factor of each number, and pick the biggest one that is in both lists.
12: 1, 2, 3, 4, 6, 12. 18: 1, 2, 3, 6, 9, 18. The biggest number in both lists is 6.
This is easy for small numbers and slow for big ones. That is what the ladder is for.
How to check your answer
The HCF has to divide both numbers exactly: 6 goes into 12 twice, and into 18 three times.
The HCF is never bigger than the smaller of the two numbers. If yours is, something has gone wrong.
Where mistakes happen
- Using a prime that divides only one of the numbers. It has to divide both.
- Stopping too early. 12 and 18 both divide by 2, and then by 3 as well. The HCF uses every prime they share.
- Mixing it up with the LCM. The HCF is never bigger than the numbers. The LCM is never smaller.
Questions people ask
Is the HCF the same as the GCF and the GCD?
Yes. They are three names for the same number.
What if one number divides the other?
Then the smaller number is the HCF. The HCF of 6 and 18 is 6.
Can the HCF be 1?
Yes. Then the two numbers are called coprime.
What is the HCF used for?
It lets you simplify a fraction in one step. Divide the top and bottom of 12/18 by their HCF, 6, and you get 2/3 straight away.