Key takeaways
- HCF(a, b) is the largest number that divides both a and b exactly.
- HCF and GCD mean the same thing — just different names in different countries.
- The Euclidean algorithm finds it fast: keep dividing and swapping until the remainder is 0.
- Two numbers with HCF = 1 are called coprime.
In this guide
What is the HCF (GCD)?
HCF stands for Highest Common Factor, also known as GCD (Greatest Common Divisor). It's the biggest number that divides both of your two numbers without leaving a remainder.
Why does the HCF matter?
The HCF lets you split things into the largest possible equal groups with nothing wasted. It's also the key step in reducing a fraction or ratio to its simplest form.
HCF(9, 16) = 1, even though neither number is prime. Numbers like these, which share no factor bigger than 1, are called coprime.
The method (Euclidean algorithm)
| Symbol | What it means | Example |
|---|---|---|
| a | The first number | 36 |
| b | The second number | 24 |
| HCF(a, b) | The greatest common divisor of a and b | 12 |
How to find the HCF step by step
- 1Divide the larger number by the smaller number and note the remainder.
- 2Replace the larger number with the smaller number, and the smaller number with the remainder.
- 3Repeat the division until the remainder becomes 0.
- 4The last non-zero remainder (the divisor at that final step) is the HCF.
Enter your own two numbers in the calculator below to see every division step.
Try it yourself
Pre-filled with the example — change any value.
Common mistakes to avoid
- Confusing HCF with LCM. HCF is the largest number that divides both numbers; LCM is the smallest number both numbers divide into.
- Listing all factors for large numbers. This works for small numbers, but the Euclidean algorithm above is much faster for bigger ones.
- Swapping the wrong numbers. In each round, the old divisor becomes the new dividend, and the remainder becomes the new divisor.
Tips and tricks
- For small numbers, listing factors of each and picking the biggest shared one works fine and can be quicker to see.
- Check your answer by dividing both original numbers by your HCF — both results should be whole numbers.
- The HCF is exactly what you need to simplify a fraction or reduce a ratio to lowest terms.
Where you'll use it in real life
- Party planning: making identical gift bags or teams using everything you have, with nothing left over.
- Cooking: finding the largest batch size that uses whole amounts of every ingredient.
- Math class: simplifying fractions and ratios to their lowest terms.
- Scheduling: working alongside the LCM to plan events that repeat on different cycles.
Quick summary
To find the HCF of two numbers, use the Euclidean algorithm: repeatedly divide and swap until the remainder hits 0 — that last divisor is your answer. It's the largest number that splits both original numbers evenly. Try the calculator above with your own two numbers.
Worked example
You have 36 chocolate bars and 24 candies, and want to make identical gift bags using all of them with nothing left over. What's the largest number of gift bags you can make?
- 01HCF(36, 24) using the Euclidean algorithm
- 0236 = 1 × 24 + 12
- 0324 = 2 × 12 + 0
- 04Remainder is 0, so HCF = 12
These numbers are pre-filled in the calculator above.
Frequently asked questions
What is the difference between HCF and GCD?
They're the same thing — HCF (Highest Common Factor) is the term used in the UK and India, while GCD (Greatest Common Divisor) is more common in the US.
What is the fastest way to find the HCF of two numbers?
Use the Euclidean algorithm: repeatedly divide the larger number by the smaller one and replace the larger number with the remainder, until the remainder reaches 0.
What is the HCF of two numbers that share no common factor besides 1?
Their HCF is 1. For example, HCF(9, 16) = 1, because no number bigger than 1 divides both evenly. These are called coprime numbers.
Can the HCF of two numbers be one of the numbers itself?
Yes, whenever one number divides evenly into the other. For example, HCF(6, 18) = 6, because 6 divides both 6 and 18 exactly.
