How to find the highest common factor
One number, three English names. Britain and India say highest common factor (HCF), the United States says greatest common factor (GCF), and greatest common divisor (GCD) is the form almost every other language uses. They all mean the same thing.
The highest common factor of two numbers is the largest whole number that divides both of them exactly.
How to do it
- Write the two numbers side by side, with a rule to the right of them.
- Find a prime that divides both numbers, not just one of them, and write it to the right of the rule.
- Divide both numbers by it and write the two answers on the next line.
- Keep going until no prime divides both. Multiply the primes down the right-hand side — that is the HCF.
Worked examples
What is the HCF of 12 and 18?
| 12 | 18 | 2 |
| 6 | 9 | 3 |
| 2 | 3 |
Nothing divides 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 goes into 8, not 15. 3 and 5 go into 15, not 8.
Nothing divides both, so the HCF is 1. Numbers like these are called coprime.
Two other ways, and when to use them
Listing works for small numbers and explains what the words mean. Write out everything that divides each number — 12 gives 1, 2, 3, 4, 6, 12 and 18 gives 1, 2, 3, 6, 9, 18 — and take the biggest that appears in both lists: 6. It is the clearest method and the first one every curriculum teaches, but it collapses quickly once the numbers grow.
Prime factors give the same answer without any listing. Break both numbers down (see how to find prime factors), then take each prime that appears in both, as many times as it appears in the one that has fewer of it. 12 = 2 × 2 × 3 and 18 = 2 × 3 × 3, so the shared part is 2 × 3 = 6.
The ladder above is just those two ideas run together. Each row peels off one shared prime, so the column of divisors is the shared part itself, already multiplied out.
Why the divisors multiply to the answer
Every prime you take out is one that divided both numbers, so their product divides both numbers too. When the row runs out, the two numbers left share nothing but 1 — there is no prime still hiding in both — so nothing bigger could have been taken. That makes the product the highest common factor rather than merely a common one.
Two checks catch most mistakes. The HCF can never be bigger than the smaller of the two numbers, and it always divides both exactly: 6 goes into 12 twice and into 18 three times.
Where mistakes happen
- Taking a prime that goes into only one of them. A common factor has to divide both, and this is the mistake that makes the answer too big.
- Stopping at the first shared prime. 12 and 18 both divide by 2, but they also both divide by 3, and the answer is the product of every shared prime.
- Giving the lowest common multiple instead. The HCF is never bigger than either number; the LCM is never smaller than either.
Questions people ask
Is HCF the same as GCF and GCD?
For whole numbers, yes — the same number under three names. HCF is British and Indian, GCF American, GCD the formal form used in most other languages.
What if one number divides the other?
Then the smaller one is the answer. The HCF of 6 and 18 is 6, because 6 divides itself and 18.
Can the HCF be 1?
Yes, and it often is. A pair whose only common factor is 1 is called coprime — two numbers picked at random are coprime about three times in five.
What is the HCF used for?
Simplifying fractions in one step. Dividing the top and bottom of 12/18 by their HCF of 6 gives 2/3 straight away, instead of halving twice and hoping.