How to Calculate HCF (GCD) Step by Step with Examples

Every Indian student meets HCF in Class 6, and again in Class 10 under Real Numbers. Yet many learners still mix up the steps or forget which method to pick. This guide shows how to calculate HCF step by step, using three clear methods and examples from daily Indian life.

You will see how a tile seller, a tailor and a school teacher all use the same idea. By the end, you will be able to solve HCF questions for school exams, NTSE, Olympiads, SSC and bank aptitude papers with confidence.

What HCF (or GCD) Means

HCF stands for Highest Common Factor. In many books and on calculators you will also see GCD, which means Greatest Common Divisor. Both names describe exactly the same number, so do not worry if your textbook uses one and your online tool uses the other.

A factor of a number divides it with no remainder. The factors of 12 are 1, 2, 3, 4, 6 and 12. A common factor is a factor shared by two or more numbers. The highest of these shared factors is the HCF.

Take 12 and 18. The factors of 12 are 1, 2, 3, 4, 6, 12. The factors of 18 are 1, 2, 3, 6, 9, 18. The common ones are 1, 2, 3 and 6, so the HCF is 6. NCERT Class 6 introduces this idea under Playing with Numbers, and CBSE Class 10 builds on it using Euclid’s division lemma.

Key takeaway: HCF is always a factor of every number in the set, so it can never be bigger than the smallest number.

Method 1: List the Factors

This is the first method children learn, and it works best for small numbers. You write down all factors of each number, circle the common ones, and pick the largest. It needs no formula, only the multiplication tables.

Steps

1. Write all factors of the first number in pairs, such as 1 and the number itself, then 2 and so on.
2. Do the same for the second number.
3. Mark the factors that appear in both lists.
4. Choose the biggest marked factor. That is the HCF.

Worked Example 1: Tiles for a Room in Pune

A room measures 420 cm by 300 cm. A contractor wants square floor tiles of the largest possible size, with no cutting. What should the tile side be, and how many tiles are needed? If one tile costs Rs. 85, what is the total cost?

The tile side must divide both 420 and 300, so we need the HCF. The factors of 300 include 1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 25, 30, 50, 60, 75, 100, 150 and 300. Checking which of these divide 420, we find that 60 works and nothing larger does (150 leaves a remainder when dividing 420). So the HCF is 60 cm.

Tiles along the length: 420 divided by 60 is 7. Tiles along the breadth: 300 divided by 60 is 5. Total tiles are 7 times 5, which is 35. The cost is 35 times Rs. 85, which is Rs. 2,975.

Listing factors is easy to understand, but it becomes slow for numbers such as 1,764 or 2,520. For those, the next two methods save a lot of time.

Method 2: Prime Factorisation

In this method you break each number into prime factors, then multiply the primes that both numbers share. For every shared prime, take the smaller power. If you need practice with the first step, a prime factorization calculator can check your factor trees.

Worked Example 2: Cloth Lengths of 504 m and 756 m

A wholesaler in Surat has two rolls of cloth, 504 m and 756 m long. He wants to cut both into pieces of equal length, as long as possible, with nothing left over. Find that length.

Step 1: Factorise 504. It is 2 times 2 times 2 times 3 times 3 times 7, which we write as 2 cubed, times 3 squared, times 7.

Step 2: Factorise 756. It is 2 times 2 times 3 times 3 times 3 times 7, which is 2 squared, times 3 cubed, times 7.

Step 3: Pick the smaller power of each common prime. For 2 the smaller power is 2 squared. For 3 it is 3 squared. For 7 it is 7 to the power 1. The HCF is 4 times 9 times 7, which is 252.

So each piece is 252 m long. The first roll gives 2 pieces and the second gives 3 pieces, 5 pieces in all. At Rs. 140 per metre, one piece is worth Rs. 35,280.

Method 3: Euclid’s Division Algorithm

Euclid’s method comes straight from the NCERT Class 10 chapter on Real Numbers. It uses Euclid’s division lemma: for any two positive integers a and b, there are whole numbers q and r so that a equals b times q, plus r, where r is at least 0 and less than b. You repeat this division until the remainder becomes zero. The last divisor is the HCF.

Steps

1. Divide the bigger number by the smaller one and note the remainder.
2. If the remainder is not zero, divide the previous divisor by this remainder.
3. Keep going until the remainder is 0.
4. The divisor in the last step is the HCF.

Worked Example 3: HCF of 867 and 255

This is a well-known NCERT-style question. Let us follow the steps.

867 divided by 255 gives quotient 3 and remainder 102, since 255 times 3 is 765. Next, 255 divided by 102 gives quotient 2 and remainder 51. Then 102 divided by 51 gives quotient 2 and remainder 0. The last divisor is 51, so the HCF of 867 and 255 is 51.

Notice how we never had to factorise 867. That is why this method is a favourite in competitive exams, where time is short.

Expert insight: Euclid’s method works because the HCF of two numbers also divides their remainder. Each step shrinks the problem until it vanishes, and the last non-zero divisor survives.

Comparing the Three Methods

Method	Best for	Speed	Main risk
Listing factors	Small numbers under 100	Slow for big numbers	Missing a factor
Prime factorisation	Two or three medium numbers	Medium	Wrong prime split
Euclid’s division	Large numbers, exam questions	Fast	Arithmetic slip in division

A good habit is to pick the method by the size of the numbers. Under 50, list the factors. Between 50 and 500, use prime factors. Above that, go straight to Euclid.

Finding the HCF of Three Numbers

The same methods extend to three or more numbers. With prime factors, you only keep primes that appear in all the numbers. With Euclid’s method, find the HCF of the first two numbers, then find the HCF of that answer and the third number.

Example: a dairy in Anand has milk cans holding 75 litres, 105 litres and 120 litres. The owner wants to fill identical smaller containers, as large as possible, with no milk left. The HCF of 75 and 105 is 15, because 105 is 75 times 1 plus 30, then 75 is 30 times 2 plus 15, then 30 is 15 times 2. Now the HCF of 15 and 120 is 15. So each container holds 15 litres. The cans need 5, 7 and 8 containers, a total of 20.

When you want to cross-check a result, a hcf calculator gives the answer instantly for two or more numbers and helps you confirm your own working.

Benefits of Knowing HCF

HCF is more than a school topic. It trains you to see how numbers fit together, and it is useful across many everyday jobs. Learning it well also makes later chapters easier.

• Simplifies fractions: dividing the top and bottom by their HCF gives the lowest form in one step.
• Saves material: carpenters, tailors and tile fitters use it to cut with no waste.
• Helps in ratios: reducing 84 to 126 to the simple ratio 2 to 3 needs the HCF 42.
• Builds exam speed: NTSE, SSC and banking papers reward quick number sense.
• Supports algebra: finding the HCF of polynomials uses the same logic.

Challenges and Limitations

HCF methods are simple, but each has limits. Listing factors becomes unreliable once numbers pass three digits, because it is easy to skip a factor. Prime factorisation can be hard when a number has a large prime factor, such as 7,919.

Euclid’s method is fast, but it needs careful division. One wrong remainder sends every later step off track. Also, HCF only applies to whole numbers. If you have decimals, such as 2.4 and 3.6, you first convert them to whole numbers by multiplying by 10, then find the HCF and divide back.

Finally, students often forget what the answer means in a word problem. The HCF gives the largest equal size, while the number of pieces needs one more division. Read the question twice to see which one is asked.

Common Mistakes to Avoid

1. Confusing HCF with LCM. HCF is the largest shared factor, while LCM is the smallest shared multiple. HCF is never bigger than the smaller number.
2. Stopping Euclid’s method too early. The HCF is the last divisor when the remainder is zero, not the last remainder.
3. Taking the larger power in prime factors. For HCF use the smaller power of each common prime.
4. Missing factors in a list. Always write factors in pairs, such as 4 and 75 for 300, so none is lost.
5. Dividing the wrong way round. In Euclid’s method the bigger number goes first as the dividend.
6. Skipping the check. Divide each number by your answer. If any remainder appears, the HCF is wrong.

Best Practices for HCF Problems

1. Choose the method first. Look at the size of the numbers before you start, and pick listing, primes or Euclid.
2. Write every step. In CBSE board exams, marks are given for the method as well as the answer.
3. Check with division. Divide each given number by the HCF and confirm there is no remainder.
4. Learn divisibility rules. Rules for 2, 3, 5, 9 and 11 make prime factorisation much faster.
5. Practise word problems. Questions on tiles, ropes and packets show up often in NTSE and SSC papers.
6. Link HCF with LCM. For two numbers, HCF times LCM equals their product. A quick lcm calculator check can confirm both answers together.

Conclusion

Finding the HCF is a skill with three reliable routes: list the factors, use prime factorisation, or run Euclid’s division. Small numbers suit the first, medium numbers suit the second, and large numbers are best handled by the third. Each method gives the same answer, so you can use one to verify the other.

Practise with real situations such as tiles, cloth rolls and milk cans, and the steps will soon feel natural. Keep the common mistakes in mind, check your answer by division, and you will be ready for school tests as well as competitive exams.

FAQs

What is the easiest way to find HCF?
For small numbers, listing factors is easiest. For bigger numbers, Euclid’s division method is quicker and has fewer steps. Pick the method that matches the size of your numbers.

Is HCF the same as GCD?
Yes. HCF means Highest Common Factor and GCD means Greatest Common Divisor. They are two names for the same value, and Indian textbooks mostly use HCF.

Can the HCF be larger than the smaller number?
No. The HCF must divide the smaller number, so it can be at most equal to it. If the smaller number divides the bigger one, the HCF is the smaller number itself.

What is the HCF of two co-prime numbers?
It is 1. Co-prime numbers share no factor other than 1. For example, 8 and 15 are co-prime, so their HCF is 1.

Where is Euclid’s division lemma used in NCERT?
It appears in Class 10, Chapter 1, Real Numbers. The chapter uses it to find the HCF of two positive integers and to prove results about numbers.