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

HCF & LCM

Study Practice Revise 🔒 Test
Learning objective
Find highest common factor and least common multiple of numbers

Introduction to HCF and LCM

In number theory, two important concepts that help us understand the relationship between numbers are the Highest Common Factor (HCF) and the Least Common Multiple (LCM). These concepts are not just theoretical; they have practical applications in daily life and competitive exams like the Delhi Police Constable (Executive) Examination.

HCF is the largest number that divides two or more numbers exactly, without leaving a remainder. It helps in simplifying fractions and solving problems related to divisibility.

LCM is the smallest number that is a multiple of two or more numbers. It is useful in scheduling events, adding fractions with different denominators, and solving problems involving repeated cycles.

Understanding how to find HCF and LCM efficiently can save time during exams and help solve a variety of numerical problems. We will explore different methods to find HCF and LCM, including prime factorization, the division method, and the Euclidean algorithm.

Prime Factorization

Prime factorization is the process of expressing a number as a product of its prime factors. A prime number is a number greater than 1 that has no divisors other than 1 and itself. For example, 2, 3, 5, 7, 11 are prime numbers.

Breaking a number into prime factors helps us find the HCF and LCM by comparing the prime factors of the numbers involved.

Let's see how to find the prime factors of 60 using a factor tree:

60 6 10 2 3 2 5 Prime Prime Prime Prime

Explanation:

  • 60 is divided into 6 and 10.
  • 6 is further divided into 2 and 3 (both prime).
  • 10 is divided into 2 and 5 (both prime).

Thus, the prime factorization of 60 is:

\[ 60 = 2 \times 2 \times 3 \times 5 \]

Or written with exponents:

\[ 60 = 2^2 \times 3^1 \times 5^1 \]

Division Method (Ladder Method)

The division method is a systematic way to find both HCF and LCM by dividing numbers simultaneously by their common prime factors until no further division is possible.

Let's illustrate this with the numbers 48 and 60:

48 60 2 24 30 2 12 15 3 4 5

Stepwise explanation:

  • Divide both 48 and 60 by 2 (common prime factor): 48 / 2 = 24, 60 / 2 = 30
  • Divide 24 and 30 again by 2: 24 / 2 = 12, 30 / 2 = 15
  • Divide 12 and 15 by 3 (next common prime factor): 12 / 3 = 4, 15 / 3 = 5
  • Now, 4 and 5 have no common prime factors other than 1, so stop.

The HCF is the product of all the divisors used: \(2 \times 2 \times 3 = 12\).

The LCM is the product of all the divisors and the remaining numbers: \(2 \times 2 \times 3 \times 4 \times 5 = 240\).

Euclidean Algorithm

The Euclidean algorithm is an efficient method to find the HCF of two numbers using repeated division and remainders. It is especially useful for large numbers where prime factorization is difficult.

The algorithm is based on the principle that the HCF of two numbers also divides their difference.

Here is a flowchart illustrating the Euclidean algorithm to find the HCF of 252 and 105:

graph TD    A[Start with numbers 252 and 105]    B[Divide 252 by 105]    C[Find remainder r = 252 mod 105 = 42]    D[Replace 252 with 105, 105 with r (42)]    E{Is remainder 0?}    F[Yes: HCF is 42]    G[No: Repeat division with new pair]    A --> B --> C --> D --> E    E -- No --> G --> B    E -- Yes --> F

Stepwise explanation:

  • Divide 252 by 105: quotient = 2, remainder = 42
  • Now find HCF of 105 and 42
  • Divide 105 by 42: quotient = 2, remainder = 21
  • Now find HCF of 42 and 21
  • Divide 42 by 21: quotient = 2, remainder = 0
  • Since remainder is 0, HCF is 21

Worked Examples

Example 1: Finding HCF and LCM of 36 and 48 Easy
Find the Highest Common Factor (HCF) and Least Common Multiple (LCM) of 36 and 48 using 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: Find common prime factors with lowest powers for HCF.

Common prime factors: 2 and 3

Lowest powers: \(2^2\) and \(3^1\)

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

Step 4: Find all prime factors with highest powers for LCM.

Highest powers: \(2^4\) and \(3^2\)

LCM = \(2^4 \times 3^2 = 16 \times 9 = 144\)

Answer: HCF = 12, LCM = 144

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

Step 1: Divide 252 by 105.

252 / 105 = 2 remainder 42

Step 2: Now find HCF of 105 and 42.

105 / 42 = 2 remainder 21

Step 3: Now find HCF of 42 and 21.

42 / 21 = 2 remainder 0

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

Answer: HCF(252, 105) = 21

Example 3: Finding LCM of 15 and 20 using HCF-LCM Relationship Easy
Given two numbers 15 and 20, find their LCM if their HCF is 5.

Step 1: Recall the formula:

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

Step 2: Substitute the known values:

5 x LCM = 15 x 20 = 300

Step 3: Solve for LCM:

LCM = \(\frac{300}{5} = 60\)

Answer: LCM of 15 and 20 is 60

Example 4: Division Method for HCF and LCM of 48, 60, and 72 Medium
Use the division method to find the HCF and LCM of 48, 60, and 72.

Step 1: Write the numbers side by side:

48, 60, 72

Step 2: Divide by 2 (common prime factor):

48 / 2 = 24, 60 / 2 = 30, 72 / 2 = 36

Step 3: Divide again by 2:

24 / 2 = 12, 30 / 2 = 15, 36 / 2 = 18

Step 4: Divide by 3:

12 / 3 = 4, 15 / 3 = 5, 18 / 3 = 6

Step 5: Divide by 2:

4 / 2 = 2, 5 / 2 = not divisible, stop dividing by 2

Step 6: Divide by 3:

2 / 3 = no, 5 / 3 = no, 6 / 3 = 2 (only one divisible, so stop)

Step 7: Remaining numbers are 2, 5, and 6

HCF: Multiply all common divisors: \(2 \times 2 \times 3 = 12\)

LCM: Multiply all divisors and remaining numbers:

LCM = \(2 \times 2 \times 3 \times 2 \times 5 \times 6 = 720\)

Answer: HCF = 12, LCM = 720

Example 5: Scheduling Problem using LCM Medium
Two events occur every 12 days and 18 days respectively. If both events happen today, after how many days will they occur together again?

Step 1: Identify the problem as finding the LCM of 12 and 18.

Step 2: Find prime factorization:

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

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

Step 3: Take highest powers of each prime for LCM:

LCM = \(2^2 \times 3^2 = 4 \times 9 = 36\)

Answer: The events will occur together again after 36 days.

HCF using Prime Factorization

\[HCF = \prod \text{(common prime factors with lowest powers)}\]

Multiply the prime factors common to all numbers with the smallest exponent

Prime factors = Prime numbers dividing all given numbers
lowest powers = Smallest exponent of each prime factor

LCM using Prime Factorization

\[LCM = \prod \text{(all prime factors with highest powers)}\]

Multiply all prime factors present in any number with the highest exponent

Prime factors = Prime numbers appearing in any of the given numbers
highest powers = Largest exponent of each prime factor

HCF-LCM Relationship

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

Used to find LCM if HCF is known, or vice versa

a, b = Two given numbers

Tips & Tricks

Tip: Use the Euclidean algorithm for large numbers to find HCF quickly.

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

Tip: Remember the formula \( \text{HCF} \times \text{LCM} = a \times b \) to find one if the other is known.

When to use: When either HCF or LCM is given and you need to find the other quickly.

Tip: Use factor trees to visually break down numbers into prime factors.

When to use: When learning prime factorization or working with smaller numbers.

Tip: For multiple numbers, find HCF and LCM pairwise or use the division method.

When to use: When dealing with three or more numbers to avoid complicated factorization.

Tip: Check divisibility rules before factorization to identify common factors quickly.

When to use: To speed up calculations and avoid unnecessary steps.

Common Mistakes to Avoid

❌ Confusing HCF with LCM and mixing their definitions.
✓ Remember that HCF is the greatest common divisor, while LCM is the smallest common multiple.
Why: Similar terminology and concepts can confuse beginners.
❌ Multiplying all prime factors instead of only common factors for HCF.
✓ For HCF, multiply only the prime factors common to all numbers with their lowest powers.
Why: Misunderstanding prime factorization leads to incorrect HCF.
❌ Forgetting to take highest powers of prime factors for LCM.
✓ Include all prime factors with their highest powers across numbers when calculating LCM.
Why: Partial factorization causes underestimation of LCM.
❌ Stopping the Euclidean algorithm too early before the remainder reaches zero.
✓ Continue the process until the remainder is zero; the last non-zero remainder is the HCF.
Why: Incomplete steps lead to wrong HCF.
❌ Dividing by non-prime numbers in the division method.
✓ Always divide by prime numbers common to all numbers at that step.
Why: Using composite numbers breaks the logic of the division method.
✨ AI exam tools — try them free (included in every plan)
Tip: select any text above to Explain / Example / Simplify it.
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 & LCM · 10 free messages
Ask me anything about this subtopic. You have 10 free messages this session — chat history isn't saved in preview.