👁 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
Study mode

HCF and LCM

Study Practice Revise 🔒 Test

Introduction to HCF and LCM

In arithmetic, two important concepts often used to solve problems are HCF and LCM. Understanding these helps in simplifying fractions, solving problems involving divisibility, and managing real-life scenarios like packaging, scheduling, and distribution.

HCF stands for Highest Common Factor. It is the greatest number that divides two or more numbers exactly without leaving a remainder.

LCM stands for Least Common Multiple. It is the smallest number that is a multiple of two or more numbers.

For example, consider the numbers 6 and 8:

  • Factors of 6: 1, 2, 3, 6
  • Factors of 8: 1, 2, 4, 8
  • Common factors: 1, 2
  • So, HCF(6, 8) = 2
  • Multiples of 6: 6, 12, 18, 24, 30, ...
  • Multiples of 8: 8, 16, 24, 32, 40, ...
  • Common multiples: 24, 48, ...
  • So, LCM(6, 8) = 24

These concepts are crucial in competitive exams and everyday calculations.

Factors and Multiples

Before diving deeper, let's understand the building blocks of HCF and LCM: factors and multiples.

Factors of a number are integers that divide the number exactly without leaving a remainder.

Multiples of a number are obtained by multiplying that number by integers (1, 2, 3, ...).

For example, consider the number 12:

  • Factors of 12: 1, 2, 3, 4, 6, 12
  • Multiples of 4: 4, 8, 12, 16, 20, ...

Notice that 12 is both a factor of itself and a multiple of 4.

0 4 8 12 16 20 24 28 32 1 2 3 4 6 12 4 8 12 16 20 24

Prime numbers are numbers greater than 1 that have only two factors: 1 and the number itself. Examples: 2, 3, 5, 7, 11, 13, ...

Prime factorization is expressing a number as a product of its prime factors. For example, 12 can be written as \( 2 \times 2 \times 3 \) or \( 2^2 \times 3 \).

Finding HCF

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

There are three common methods to find HCF:

1. Listing Factors Method

List all factors of the numbers and find the greatest common one.

Example: Find HCF of 18 and 24.

  • Factors of 18: 1, 2, 3, 6, 9, 18
  • Factors of 24: 1, 2, 3, 4, 6, 8, 12, 24
  • Common factors: 1, 2, 3, 6
  • HCF = 6

This method is simple but can be time-consuming for large numbers.

2. Prime Factorization Method

Express each number as a product of prime factors, then multiply the common prime factors with the smallest powers.

Example: Find HCF of 48 and 60.

  • 48 = \( 2^4 \times 3 \)
  • 60 = \( 2^2 \times 3 \times 5 \)
  • Common prime factors: 2 and 3
  • Take minimum powers: \( 2^{2} \) and \( 3^{1} \)
  • HCF = \( 2^2 \times 3 = 4 \times 3 = 12 \)

3. Euclidean Algorithm

This is an efficient method for large numbers based on the principle that HCF of two numbers also divides their difference.

Steps:

  1. Divide the larger number by the smaller number.
  2. Replace the larger number with the smaller number and the smaller number with the remainder.
  3. Repeat until the remainder is zero.
  4. The last non-zero remainder is the HCF.
graph TD    A[Start with numbers a and b, a > b] --> B[Divide a by b]    B --> C{Remainder r = 0?}    C -- No --> D[Set a = b, b = r]    D --> B    C -- Yes --> E[HCF is b]

This method is fast and suitable for competitive exams.

Finding LCM

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

Methods to find LCM include:

1. Listing Multiples Method

List multiples of each number until you find the smallest common one.

Example: Find LCM of 5 and 7.

  • Multiples of 5: 5, 10, 15, 20, 25, 30, 35, ...
  • Multiples of 7: 7, 14, 21, 28, 35, 42, ...
  • LCM = 35

This method is easy but inefficient for large numbers.

2. Prime Factorization Method

Find the prime factors of each number, then multiply the prime factors with the highest powers.

Example: Find LCM of 12 and 18.

  • 12 = \( 2^2 \times 3 \)
  • 18 = \( 2 \times 3^2 \)
  • Take maximum powers: \( 2^2 \) and \( 3^2 \)
  • LCM = \( 2^2 \times 3^2 = 4 \times 9 = 36 \)

3. Using Relation Between HCF and LCM

For two numbers \(a\) and \(b\),

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

If you know the HCF and the numbers, you can find the LCM quickly.

Method Advantages Disadvantages
Listing Multiples Simple for small numbers Time-consuming for large numbers
Prime Factorization Accurate and systematic Requires knowledge of prime factors
Using HCF Relation Fast when HCF is known Only for two numbers

Worked Examples

Example 1: Finding HCF and LCM of 24 and 36 Easy
Find the Highest Common Factor (HCF) and Least Common Multiple (LCM) of 24 and 36 using prime factorization.

Step 1: Find prime factorization of each number.

24 = \( 2^3 \times 3 \)

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

Step 2: For HCF, take the minimum powers of common primes.

Common primes: 2 and 3

Minimum powers: \( 2^{2} \) and \( 3^{1} \)

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

Step 3: For LCM, take the maximum powers of all primes involved.

Maximum powers: \( 2^{3} \) and \( 3^{2} \)

LCM = \( 2^3 \times 3^2 = 8 \times 9 = 72 \)

Answer: HCF = 12, LCM = 72

Example 2: Using Euclidean Algorithm to find HCF of 252 and 105 Medium
Find the HCF of 252 and 105 using the Euclidean algorithm.

Step 1: Divide 252 by 105.

252 / 105 = 2 remainder 42 (because \( 105 \times 2 = 210 \), \( 252 - 210 = 42 \))

Step 2: Now divide 105 by 42.

105 / 42 = 2 remainder 21 (since \( 42 \times 2 = 84 \), \( 105 - 84 = 21 \))

Step 3: Divide 42 by 21.

42 / 21 = 2 remainder 0

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

Answer: HCF(252, 105) = 21

Example 3: Finding LCM of 15, 20, and 30 using prime factorization Medium
Find the LCM of 15, 20, and 30 using prime factorization.

Step 1: Find prime factorization of each number.

15 = \( 3 \times 5 \)

20 = \( 2^2 \times 5 \)

30 = \( 2 \times 3 \times 5 \)

Step 2: Take the highest powers of all primes involved.

  • Prime 2: highest power is \( 2^2 \) (from 20)
  • Prime 3: highest power is \( 3^1 \) (from 15 and 30)
  • Prime 5: highest power is \( 5^1 \) (all numbers)

Step 3: Multiply these highest powers.

LCM = \( 2^2 \times 3 \times 5 = 4 \times 3 \times 5 = 60 \)

Answer: LCM(15, 20, 30) = 60

Example 4: Word Problem: Packaging items in INR and metric units Hard
A shopkeeper has packets of rice weighing 12 kg and 18 kg. He wants to pack them into smaller packets of equal weight without any rice left over. What is the greatest possible weight of each smaller packet? Also, if the price per kg of rice is Rs.50, what is the least amount he can charge for one smaller packet?

Step 1: Find the HCF of 12 kg and 18 kg to determine the greatest possible weight of each smaller packet.

Prime factorization:

12 = \( 2^2 \times 3 \)

18 = \( 2 \times 3^2 \)

HCF = \( 2^{\min(2,1)} \times 3^{\min(1,2)} = 2^1 \times 3^1 = 6 \) kg

Step 2: Each smaller packet weighs 6 kg.

Step 3: Calculate the price of one smaller packet.

Price per kg = Rs.50

Price per packet = \( 6 \times 50 = Rs.300 \)

Answer: The greatest possible weight of each smaller packet is 6 kg, and the least price per packet is Rs.300.

Example 5: Using relation between HCF and LCM to find missing value Medium
Two numbers are 36 and 60. Their HCF is 12. Find their LCM using the relation between HCF and LCM.

Step 1: Use the formula:

\[ \text{HCF} \times \text{LCM} = \text{Product of the two numbers} \]

Step 2: Substitute the known values:

12 x LCM = 36 x 60

12 x LCM = 2160

Step 3: Divide both sides by 12:

LCM = \( \frac{2160}{12} = 180 \)

Answer: LCM of 36 and 60 is 180.

Formula Bank

Relation between HCF and LCM
\[ \text{HCF}(a,b) \times \text{LCM}(a,b) = a \times b \]
where: \(a,b\) = two given numbers
Prime Factorization for HCF
\[ \text{HCF} = \prod p_i^{\min(e_i,f_i)} \]
where: \(p_i\) = prime factors, \(e_i\) and \(f_i\) = exponents in factorization of numbers
Prime Factorization for LCM
\[ \text{LCM} = \prod p_i^{\max(e_i,f_i)} \]
where: \(p_i\) = prime factors, \(e_i\) and \(f_i\) = exponents in factorization of numbers

Tips & Tricks

Tip: Use the Euclidean Algorithm for finding HCF quickly when numbers are large.

When to use: For large numbers where listing factors is impractical.

Tip: Remember the relation \( \text{HCF} \times \text{LCM} = \text{product of two numbers} \) to find missing values fast.

When to use: When either HCF or LCM is known along with the two numbers.

Tip: Use prime factorization to find HCF and LCM of more than two numbers efficiently.

When to use: When dealing with three or more numbers.

Tip: Memorize divisibility rules for 2, 3, 5, 7, and 11 to speed up prime factorization.

When to use: To quickly factorize numbers during exams.

Tip: Check if one number divides the other completely to quickly find HCF.

When to use: When one number is clearly a multiple of the other.

Common Mistakes to Avoid

❌ Confusing factors with multiples
✓ Remember factors divide the number exactly, multiples are products of the number.
Why: Mixing these concepts leads to incorrect HCF or LCM calculations.
❌ Using listing method for large numbers causing errors and delays
✓ Use Euclidean algorithm or prime factorization for accuracy and speed.
Why: Listing factors or multiples for large numbers is time-consuming and error-prone.
❌ Applying the formula \( \text{HCF} \times \text{LCM} = \text{product of numbers} \) for more than two numbers
✓ Use this formula only for two numbers, not for three or more.
Why: The formula is valid only for two numbers; generalizing it causes wrong answers.
❌ Ignoring common prime factors when calculating HCF
✓ Always take minimum powers of common prime factors for HCF.
Why: Ignoring this leads to overestimating the HCF.
❌ Taking maximum powers of primes for HCF instead of minimum
✓ Remember: HCF uses minimum powers, LCM uses maximum powers of prime factors.
Why: Confusing the rules for HCF and LCM prime factorization causes errors.
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.