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

HCF and LCM

Study Practice Revise 🔒 Test

Introduction to HCF and LCM

When we work with numbers, two important ideas often help us solve many problems: factors and multiples. Understanding these ideas leads us to two special numbers called the Highest Common Factor (HCF) and the Least Common Multiple (LCM).

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

Multiples of a number are the numbers you get when you multiply it by 1, 2, 3, and so on. For example, multiples of 5 are 5, 10, 15, 20, 25, and so on.

The Highest Common Factor (HCF) of two or more numbers is the largest number that divides all of them exactly. For example, the HCF of 12 and 18 is 6.

The Least Common Multiple (LCM) of two or more numbers is the smallest number that is a multiple of all of them. For example, the LCM of 4 and 6 is 12.

These concepts are very useful in everyday life. For example, if two buses leave a bus stop at different intervals and you want to know when they will leave together again, you use LCM. If you want to divide something into equal parts without leftovers, you use HCF.

Factors and Multiples

Let's explore factors and multiples more deeply.

What are Factors?

A factor of a number is any number that divides it exactly. For example, consider 24:

  • 1 divides 24 (24 / 1 = 24)
  • 2 divides 24 (24 / 2 = 12)
  • 3 divides 24 (24 / 3 = 8)
  • 4 divides 24 (24 / 4 = 6)
  • 6 divides 24 (24 / 6 = 4)
  • 8 divides 24 (24 / 8 = 3)
  • 12 divides 24 (24 / 12 = 2)
  • 24 divides 24 (24 / 24 = 1)

So, factors of 24 are: 1, 2, 3, 4, 6, 8, 12, 24.

What are Multiples?

A multiple of a number is what you get when you multiply the number by 1, 2, 3, and so on. For example, multiples of 7 are:

  • 7 x 1 = 7
  • 7 x 2 = 14
  • 7 x 3 = 21
  • 7 x 4 = 28
  • 7 x 5 = 35

So, multiples of 7 are 7, 14, 21, 28, 35, and so on.

Prime and Composite Numbers

A prime number is a number greater than 1 that has only two factors: 1 and itself. For example, 2, 3, 5, 7, 11 are prime numbers.

A composite number is a number that has more than two factors. For example, 4, 6, 8, 9, 12 are composite numbers.

Divisibility Rules

Divisibility rules help us quickly check if a number is divisible by another without doing full division. Here are some useful rules:

  • Divisible by 2: If the last digit is even (0, 2, 4, 6, 8).
  • Divisible by 3: If the sum of digits is divisible by 3.
  • Divisible by 5: If the last digit is 0 or 5.
  • Divisible by 9: If the sum of digits is divisible by 9.
36 4 9 2 2 3 3 Factor Tree of 36 Multiples of 5 5 x 1 = 5 5 x 2 = 10 5 x 3 = 15 5 x 4 = 20 5 x 5 = 25 5 x 6 = 30 5 x 7 = 35

Highest Common Factor (HCF)

The Highest Common Factor (HCF) of two or more numbers is the greatest number that divides all of them exactly.

Why is HCF important? It helps us simplify fractions, divide things into equal parts, and solve many real-life problems like sharing or grouping.

Methods to Find HCF

1. Prime Factorization Method

Break each number into its prime factors. The HCF is the product of all prime factors common to all numbers, taken with the smallest power.

2. Division Method

Divide the larger number by the smaller number, then divide the divisor by the remainder. Repeat until the remainder is zero. The last divisor is the HCF.

3. Euclid's Algorithm

This is a fast method based on the division method. It uses the fact that HCF of two numbers also divides their difference.

graph TD    A[Start with numbers a and b, a > b]    B[Divide a by b]    C[Find remainder r = a mod b]    D{Is r = 0?}    E[HCF is b]    F[Set a = b, b = r]    G[Repeat division]    A --> B    B --> C    C --> D    D -- Yes --> E    D -- No --> F    F --> G    G --> B

Least Common Multiple (LCM)

The Least Common Multiple (LCM) of two or more numbers is the smallest number that is a multiple of all of them.

LCM is useful in problems involving synchronization, such as finding when two events will happen together again, or adding fractions with different denominators.

Methods to Find LCM

1. Prime Factorization Method

Break each number into prime factors. The LCM is the product of all prime factors involved, taken with the highest power.

2. Listing Multiples

List multiples of each number and find the smallest common multiple.

Multiples of 4 and 6
4 6
46
812
1218
1624
2030
2436

Here, the smallest common multiple is 12, so LCM(4,6) = 12.

3. Using the Relation between HCF and LCM

There is a useful formula connecting HCF and LCM:

Relationship between HCF and LCM

\[HCF(a,b) \times LCM(a,b) = a \times b\]

The product of the HCF and LCM of two numbers equals the product of the numbers themselves.

a,b = two integers

This formula helps find one if the other is known.

Relationship between HCF and LCM

For any two positive integers \(a\) and \(b\), the product of their HCF and LCM is equal to the product of the numbers themselves:

\[\text{HCF}(a,b) \times \text{LCM}(a,b) = a \times b\]

This relationship is very useful in calculations and problem-solving.

Summary of HCF and LCM

  • HCF is the greatest common divisor of numbers.
  • LCM is the smallest common multiple of numbers.
  • Prime factorization helps find both HCF and LCM.
  • Euclid's algorithm is a fast way to find HCF.
  • HCF x LCM = Product of the two numbers.
Key Takeaway:

Understanding HCF and LCM helps solve many real-life and exam problems efficiently.

Formula Bank

Formula Bank

HCF by 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 \(p_i\) in the two numbers
LCM by Prime Factorization
\[ \text{LCM} = \prod_{i} p_i^{\max(a_i,b_i)} \]
where: \(p_i\) = prime factors; \(a_i, b_i\) = powers of prime \(p_i\) in the two numbers
Relationship between HCF and LCM
\[ \text{HCF}(a,b) \times \text{LCM}(a,b) = a \times b \]
where: \(a,b\) = two integers
Euclid's Algorithm
\[ \text{HCF}(a,b) = \text{HCF}(b, a \bmod b) \]
where: \(a,b\) = two integers; \(a \bmod b\) = remainder when \(a\) is divided by \(b\)

Worked Examples

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

Step 1: Find prime factors of 36.

36 = 2 x 2 x 3 x 3 = \(2^2 \times 3^2\)

Step 2: Find prime factors of 48.

48 = 2 x 2 x 2 x 2 x 3 = \(2^4 \times 3^1\)

Step 3: Identify common prime factors with smallest powers.

Common prime factors: 2 and 3.

Smallest power of 2: \(2^2\)

Smallest power of 3: \(3^1\)

Step 4: Multiply these to get HCF.

HCF = \(2^2 \times 3^1 = 4 \times 3 = 12\)

Answer: HCF of 36 and 48 is 12.

Example 2: LCM of 4 and 6 by Listing Multiples Easy
Find the Least Common Multiple (LCM) of 4 and 6 by listing their multiples.

Step 1: List multiples of 4: 4, 8, 12, 16, 20, 24, ...

Step 2: List multiples of 6: 6, 12, 18, 24, 30, ...

Step 3: Identify common multiples: 12, 24, ...

Step 4: Choose the smallest common multiple.

LCM = 12

Answer: LCM of 4 and 6 is 12.

Example 3: HCF of 252 and 105 using Euclid's Algorithm Medium
Find the HCF of 252 and 105 using Euclid's algorithm.

Step 1: Divide 252 by 105.

252 / 105 = 2 remainder 42 (since 105 x 2 = 210, 252 - 210 = 42)

Step 2: Now find HCF(105, 42).

Divide 105 by 42.

105 / 42 = 2 remainder 21 (42 x 2 = 84, 105 - 84 = 21)

Step 3: Now find HCF(42, 21).

Divide 42 by 21.

42 / 21 = 2 remainder 0

Step 4: Since remainder is 0, HCF is 21.

Answer: HCF of 252 and 105 is 21.

Example 4: LCM of 15 and 20 using HCF Medium
Find the LCM of 15 and 20, given that their HCF is 5.

Step 1: Use the formula:

\[ \text{LCM} = \frac{a \times b}{\text{HCF}} \]

Step 2: Substitute values:

\[ \text{LCM} = \frac{15 \times 20}{5} = \frac{300}{5} = 60 \]

Answer: LCM of 15 and 20 is 60.

Example 5: Scheduling Problem - Events every 12 and 15 days Hard
Two events occur every 12 days and 15 days respectively. If both occur today, after how many days will they occur together again?

Step 1: Find the LCM of 12 and 15.

Prime factors of 12 = \(2^2 \times 3\)

Prime factors of 15 = \(3 \times 5\)

Step 2: Take highest powers of all primes:

\(2^2\), \(3^1\), \(5^1\)

Step 3: Calculate LCM:

\[ \text{LCM} = 2^2 \times 3 \times 5 = 4 \times 3 \times 5 = 60 \]

Step 4: So, both events will occur together after 60 days.

Answer: The events coincide every 60 days.

Tips & Tricks

Tip: Use prime factorization for smaller numbers and Euclid's algorithm for larger numbers.

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

Tip: Memorize divisibility rules for 2, 3, 5, and 9 to quickly identify factors.

When to use: To speed up factorization during exams.

Tip: Use the relationship HCF x LCM = product of numbers to find one if the other is known.

When to use: When either HCF or LCM is given and the other needs to be found.

Tip: For LCM, listing multiples is practical only for small numbers; avoid for large numbers.

When to use: When numbers are small and quick mental calculation is possible.

Tip: In word problems, identify whether HCF or LCM is required by understanding the context (division or synchronization).

When to use: To correctly approach application-based problems.

Common Mistakes to Avoid

❌ Confusing HCF with LCM and using the wrong method.
✓ Remember HCF is about common factors (dividing), LCM is about common multiples (multiplying).
Why: Students often confuse the two because both involve commonality but in opposite senses.
❌ Not using prime factorization correctly, missing common prime factors.
✓ Carefully break down numbers into all prime factors and compare powers.
Why: Rushing leads to incomplete factorization and incorrect HCF/LCM.
❌ Using listing multiples method for large numbers causing time wastage.
✓ Switch to prime factorization or Euclid's algorithm for efficiency.
Why: Listing multiples grows exponentially and is impractical for large inputs.
❌ Forgetting to apply the HCF x LCM = product formula correctly (e.g., mixing up numbers).
✓ Write the formula clearly and substitute values carefully.
Why: Carelessness in substitution leads to wrong answers.
❌ Misinterpreting word problems and choosing wrong approach (HCF vs LCM).
✓ Analyze problem context carefully to decide whether to find HCF or LCM.
Why: Lack of understanding of problem context causes incorrect application.
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
HCF and LCM · 10 free messages
Ask me anything about this subtopic. You have 10 free messages this session — chat history isn't saved in preview.