👁 Preview — Study, Practice and Revise are open; mock tests and the rest of the syllabus unlock on subscription. Unlock all · ₹4,999
← Back to Arithmetic Operations
Study mode

Highest Common Factor (HCF)

Study Practice Revise 🔒 Test
Learning objective
Find the highest common factor of given numbers

Understanding Highest Common Factor (HCF)

Before we learn how to find the Highest Common Factor (HCF) of numbers, let's first understand what factors are.

Factors of a number are the numbers that divide it exactly without leaving any remainder. For example, factors of 12 are 1, 2, 3, 4, 6, and 12 because each divides 12 completely.

When we look at two or more numbers, some factors may be common to all of them. These are called common factors. For example, the factors of 12 are 1, 2, 3, 4, 6, 12 and the factors of 18 are 1, 2, 3, 6, 9, 18. The common factors of 12 and 18 are 1, 2, 3, and 6.

The Highest Common Factor (HCF) is the greatest number among the common factors. In the example above, the HCF of 12 and 18 is 6.

Why is HCF important? It helps us simplify fractions, solve problems involving ratios, and divide things into equal parts without leftovers. For example, if you want to cut two ropes into equal pieces without any leftover, the length of each piece will be the HCF of the lengths of the ropes.

Visualizing Factors and Common Factors

Imagine two sets of blocks representing the factors of two numbers. The blocks that appear in both sets are the common factors. The largest block in this overlap is the HCF.

Methods to Find the Highest Common Factor (HCF)

There are three main methods to find the HCF of two or more numbers:

  • Prime Factorization Method
  • Division Method
  • Euclidean Algorithm

We will learn each method step-by-step with examples.

Prime Factorization Method

This method involves breaking down each number into its prime factors. A prime number is a number greater than 1 that has no factors other than 1 and itself (like 2, 3, 5, 7, 11, etc.).

Once we find the prime factors of each number, we look for the common prime factors. The HCF is the product of these common prime factors, each taken with the smallest power (or count) they appear in.

Let's see how to do this with an example.

36 6 6 2 3 2 3 48 6 8 2 3 2 4 2 2

In the factor trees above:

  • 36 breaks down into prime factors: 2, 2, 3, 3
  • 48 breaks down into prime factors: 2, 2, 2, 3

The common prime factors are two 2's and one 3.

So, the HCF is \( 2 \times 2 \times 3 = 12 \).

Division Method

This method uses repeated division to find the HCF. Here's how it works:

  1. Divide the larger number by the smaller number.
  2. If the remainder is zero, the divisor is the HCF.
  3. If the remainder is not zero, replace the larger number with the smaller number, and the smaller number with the remainder.
  4. Repeat the process until the remainder is zero.
graph TD    A[Start with two numbers: a (larger), b (smaller)]    B[Divide a by b]    C{Is remainder zero?}    D[Yes: HCF is b]    E[No: Replace a with b, b with remainder]    F[Repeat division]    A --> B --> C    C -->|Yes| D    C -->|No| E --> F --> C

This method is straightforward and works well for numbers where division is easy.

Euclidean Algorithm

The Euclidean algorithm is a faster and more efficient way to find the HCF, especially for large numbers. It is based on the principle:

HCF(a, b) = HCF(b, a mod b)

where \( a \mod b \) is the remainder when \( a \) is divided by \( b \).

You keep applying this formula repeatedly until the remainder becomes zero. The last non-zero divisor is the HCF.

graph TD    A[Start with numbers a and b]    B[Calculate remainder r = a mod b]    C{Is r zero?}    D[Yes: HCF is b]    E[No: Set a = b, b = r]    F[Repeat calculation]    A --> B --> C    C -->|Yes| D    C -->|No| E --> F --> B

This method is very useful in exams because it reduces the problem quickly without full factorization.

Worked Examples

Example 1: HCF of 36 and 48 by Prime Factorization Easy
Find the Highest Common Factor (HCF) of 36 and 48 using prime factorization.

Step 1: Find the prime factors of 36.

36 = 2 x 2 x 3 x 3

Step 2: Find the prime factors of 48.

48 = 2 x 2 x 2 x 3

Step 3: Identify the common prime factors.

Common prime factors are two 2's and one 3.

Step 4: Multiply the common prime factors to get the HCF.

HCF = 2 x 2 x 3 = 12

Answer: The HCF of 36 and 48 is 12.

Example 2: HCF of 56 and 98 by Division Method Medium
Find the HCF of 56 and 98 using the division method.

Step 1: Divide the larger number 98 by the smaller number 56.

98 / 56 = 1 remainder 42

Step 2: Now divide 56 by the remainder 42.

56 / 42 = 1 remainder 14

Step 3: Divide 42 by the remainder 14.

42 / 14 = 3 remainder 0

Step 4: Since the remainder is 0, the divisor 14 is the HCF.

Answer: The HCF of 56 and 98 is 14.

Example 3: HCF of 270 and 192 by Euclidean Algorithm Medium
Use the Euclidean algorithm to find the HCF of 270 and 192.

Step 1: Calculate 270 mod 192.

270 / 192 = 1 remainder 78, so 270 mod 192 = 78

Step 2: Now find HCF(192, 78).

192 / 78 = 2 remainder 36, so 192 mod 78 = 36

Step 3: Find HCF(78, 36).

78 / 36 = 2 remainder 6, so 78 mod 36 = 6

Step 4: Find HCF(36, 6).

36 / 6 = 6 remainder 0, so 36 mod 6 = 0

Step 5: Since remainder is 0, HCF is 6.

Answer: The HCF of 270 and 192 is 6.

Example 4: Simplifying Fraction 84/126 Easy
Simplify the fraction \(\frac{84}{126}\) by finding the HCF of numerator and denominator.

Step 1: Find the HCF of 84 and 126.

Factors of 84: 1, 2, 3, 4, 6, 7, 12, 14, 21, 28, 42, 84

Factors of 126: 1, 2, 3, 6, 7, 9, 14, 18, 21, 42, 63, 126

Common factors: 1, 2, 3, 6, 7, 14, 21, 42

Highest common factor is 42.

Step 2: Divide numerator and denominator by 42.

\(\frac{84}{42} = 2\), \(\frac{126}{42} = 3\)

Answer: Simplified fraction is \(\frac{2}{3}\).

Example 5: Cutting Ropes of 150 cm and 210 cm Hard
Two ropes of lengths 150 cm and 210 cm need to be cut into equal pieces without any leftover. Find the maximum length of each piece.

Step 1: Find the HCF of 150 and 210.

Prime factors of 150: 2 x 3 x 5 x 5

Prime factors of 210: 2 x 3 x 5 x 7

Common prime factors: 2, 3, 5

HCF = 2 x 3 x 5 = 30

Step 2: The maximum length of each piece is 30 cm.

Answer: Each piece should be 30 cm long.

Formula Bank

HCF using Prime Factorization
\[ \text{HCF} = \prod_{i} p_i^{\min(a_i, b_i)} \]
where: \( p_i \) = prime factors; \( a_i, b_i \) = powers of prime factor \( p_i \) in each number
HCF using Euclidean Algorithm
\[ \text{HCF}(a, b) = \text{HCF}(b, a \bmod b), \quad \text{repeat until } b=0 \]
where: \( a, b \) = two positive integers; \( a \bmod b \) = remainder when \( a \) is divided by \( b \)

Tips & Tricks

Tip: Use prime factorization for small numbers and Euclidean algorithm for large numbers.

When to use: When numbers are large or prime factorization is time-consuming.

Tip: Remember that HCF divides both numbers exactly without remainder.

When to use: To verify answers quickly in any method.

Tip: For division method, always divide the larger number by the smaller one first.

When to use: To avoid confusion and speed up calculations.

Tip: Use the Euclidean algorithm's recursive formula to save time in exams.

When to use: When under time pressure in competitive exams.

Tip: Check for common prime factors by starting with the smallest primes (2, 3, 5).

When to use: During prime factorization to avoid missing factors.

Common Mistakes to Avoid

❌ Confusing HCF with LCM
✓ Remember HCF is the greatest common divisor, LCM is the smallest common multiple.
Why: Both involve common factors but serve different purposes.
❌ Not including all common prime factors in prime factorization
✓ Include only the prime factors common to both numbers with the lowest powers.
Why: Including non-common factors inflates the HCF incorrectly.
❌ Stopping division method too early before remainder reaches zero
✓ Continue dividing until remainder is zero; the last divisor is the HCF.
Why: Premature stopping leads to incorrect HCF.
❌ Mixing up dividend and divisor in Euclidean algorithm steps
✓ Always replace (a, b) with (b, a mod b), not the other way around.
Why: Incorrect order disrupts the recursive process.
❌ Forgetting to simplify fractions after finding HCF
✓ Divide numerator and denominator by HCF to simplify fraction fully.
Why: Simplification is the practical application of HCF.

Key Takeaways

  • HCF is the greatest number that divides two or more numbers exactly.
  • Prime factorization involves breaking numbers into prime factors and multiplying common ones.
  • Division method uses repeated division until remainder is zero; last divisor is HCF.
  • Euclidean algorithm is a fast recursive method using remainders.
  • HCF helps simplify fractions and solve real-life problems involving equal division.
Key Takeaway:

Mastering these methods and avoiding common mistakes will help you solve HCF problems confidently and quickly.

Curated videos per subtopic
Top YouTube explainers, AI-ranked for your exam and language. Unlocks with subscription.
Unlock

Try Practice next.

Progress tracking is paywalled — subscribe to mark subtopics as understood and save your streak.

Go to practice →
Ask a doubt
Highest Common Factor (HCF) · 10 free messages
Ask me anything about this subtopic. You have 10 free messages this session — chat history isn't saved in preview.