0
0

Factors & Multiples (HCF & LCM)

Introduction

Factors and multiples are essential tools for simplifying fractions, solving divisibility problems, and scheduling repeating events. Finding the Highest Common Factor (HCF / GCD) and Least Common Multiple (LCM) quickly saves time in aptitude tests and competitive exams.

Pattern: Factors & Multiples (HCF & LCM)

Pattern

Compute HCF by taking common prime powers with minimum exponents; compute LCM by taking all prime powers with maximum exponents. Use Euclid’s algorithm for fast GCD and the product identity to get LCM.

  • Factor: d is a factor of n if n ÷ d is integer.
  • Multiple: m is a multiple of n if m = n × k for some integer k.
  • Prime factorization: Write numbers as products of primes:
    a = ∏ p_i^{α_i}, b = ∏ p_i^{β_i} (use exponent 0 if prime absent).
  • HCF/GCD (prime-power formula):
    HCF(a,b) = ∏ p_i^{min(α_i,β_i)}.
  • LCM (prime-power formula):
    LCM(a,b) = ∏ p_i^{max(α_i,β_i)}.
  • Product identity (two numbers):
    HCF(a,b) × LCM(a,b) = |a × b|.
  • Euclidean algorithm (fast GCD):
    gcd(a,b) = gcd(b, a mod b). Repeat until remainder = 0; last nonzero divisor is gcd.
  • LCM from GCD:
    LCM(a,b) = |a × b| / GCD(a,b).
  • Extend to many numbers:
    GCD(a,b,c) = GCD(GCD(a,b),c). LCM(a,b,c) = LCM(LCM(a,b),c).

Step-by-Step Example

Question

Find the HCF (GCD) and LCM of 84 and 108.

Solution

  1. Step 1: Prime factorization:

    84 = 2 × 42 = 2^2 × 3 × 7 → 84 = 22 × 31 × 71.
    108 = 2 × 54 = 2^2 × 3 × 27 = 2^2 × 3^3 → 108 = 22 × 33.

  2. Step 2: Compute HCF using min exponents:

    HCF(84,108) = 2min(2,2) × 3min(1,3) × 7min(1,0) = 22 × 31 × 70 = 4 × 3 × 1 = 12.

  3. Step 3: Compute LCM using max exponents:

    LCM(84,108) = 2max(2,2) × 3max(1,3) × 7max(1,0) = 22 × 33 × 71 = 4 × 27 × 7 = 756.

  4. Step 4: Verify with product identity (Quick Check):

    84 × 108 = 9072. HCF × LCM = 12 × 756 = 9072 → matches. ✅

  5. Final Answer:

    HCF(84,108) = 12. LCM(84,108) = 756.

  6. Quick Check:

    756 ÷ 84 = 9 (integer) and 756 ÷ 108 = 7 (integer). 12 divides both 84 and 108. Product identity holds. ✅

Quick Variations

1. Use Euclidean algorithm for large numbers: e.g., gcd(108,84) → gcd(84,24) → gcd(24,12) → gcd(12,0) = 12.

2. For three numbers a,b,c: compute GCD iteratively: GCD(a,b,c)=GCD(GCD(a,b),c) and similarly for LCM.

3. If numbers are co-prime (GCD = 1), then LCM = product of numbers.

Trick to Always Use

  • Step 1 → Try Euclidean algorithm for GCD first (fast and avoids full factorization).
  • Step 2 → Use LCM = |a × b| / GCD(a,b) to compute LCM quickly.
  • Step 3 → For small numbers, prime factorization and min/max exponent rule is clear and reliable.
  • Step 4 → For many numbers, compute pairwise iteratively rather than factoring all at once.

Summary

Summary

  • Find HCF using prime powers with minimum exponents or by applying the Euclidean algorithm.
  • Find LCM using prime powers with maximum exponents or by applying LCM = |a × b| / GCD.
  • The product identity HCF × LCM = |a × b| always holds for two numbers.
  • Extend both GCD and LCM to many numbers by applying the operations iteratively.

Example to remember:
For 84 and 108, HCF = 12 and LCM = 756 because min/max prime exponents give exact values, and 12 × 756 = 9072 = 84 × 108.

Practice

(1/5)
1. Find the HCF (GCD) of 18 and 24.
easy
A. 6
B. 12
C. 3
D. 2

Solution

  1. Step 1: Prime factorize:

    18 = 2 × 3^2; 24 = 2^3 × 3.

  2. Step 2: Take minimum exponents for common primes:

    Common primes: 2 and 3. Min powers → 2^{min(1,3)} × 3^{min(2,1)} = 2^1 × 3^1 = 6.

  3. Final Answer:

    HCF(18,24) = 6 → Option A.

  4. Quick Check:

    6 divides 18 (18 ÷ 6 = 3) and 24 (24 ÷ 6 = 4). No larger common divisor exists. ✅
Hint: Prime-factorize and take min exponents for common primes.
Common Mistakes: Using LCM logic (max exponents) instead of min exponents for HCF.
2. Find the LCM of 9 and 12.
easy
A. 18
B. 36
C. 54
D. 48

Solution

  1. Step 1: Prime factorize:

    9 = 3^2; 12 = 2^2 × 3.

  2. Step 2: Take maximum exponents across primes:

    Primes: 2 and 3. Max powers → 2^{max(0,2)} × 3^{max(2,1)} = 2^2 × 3^2 = 4 × 9 = 36.

  3. Final Answer:

    LCM(9,12) = 36 → Option B.

  4. Quick Check:

    36 ÷ 9 = 4 and 36 ÷ 12 = 3 → both integers, and 36 is the smallest such number. ✅
Hint: Use prime-factorization and take max exponents for LCM.
Common Mistakes: Multiplying numbers directly without dividing by GCD when applicable.
3. Find the LCM of 6 and 10.
easy
A. 20
B. 12
C. 30
D. 60

Solution

  1. Step 1: Prime factorize:

    6 = 2 × 3; 10 = 2 × 5.

  2. Step 2: Take maximum exponents:

    Primes involved: 2, 3, 5 → 2^{1} × 3^{1} × 5^{1} = 2 × 3 × 5 = 30.

  3. Final Answer:

    LCM(6,10) = 30 → Option C.

  4. Quick Check:

    30 ÷ 6 = 5 and 30 ÷ 10 = 3 → both integers and 30 is smallest such number. ✅
Hint: LCM = product of distinct prime factors raised to their highest powers.
Common Mistakes: Choosing product (60) without reducing by common factors (GCD).
4. Find GCD(270, 192) using the Euclidean algorithm.
medium
A. 12
B. 3
C. 9
D. 6

Solution

  1. Step 1: Apply Euclidean algorithm:

    Compute remainders: 270 ÷ 192 → remainder 78 (270 - 192 = 78).

  2. Step 2: Continue:

    192 ÷ 78 → remainder 36 (192 - 2×78 = 36). 78 ÷ 36 → remainder 6 (78 - 2×36 = 6). 36 ÷ 6 → remainder 0.

  3. Final Answer:

    When remainder becomes 0, last non-zero remainder is GCD → 6 → Option D.

  4. Quick Check:

    6 divides 270 (270 ÷ 6 = 45) and 192 (192 ÷ 6 = 32). ✅
Hint: Use repeated remainder steps: gcd(a,b)=gcd(b,a mod b) until remainder 0.
Common Mistakes: Stopping too early or making arithmetic error in remainder steps.
5. Find the LCM of 8, 12 and 20.
medium
A. 120
B. 60
C. 240
D. 40

Solution

  1. Step 1: Prime factorize:

    8 = 2^3; 12 = 2^2 × 3; 20 = 2^2 × 5.

  2. Step 2: Take maximum exponents for each prime:

    Primes: 2, 3, 5 → 2^{max(3,2,2)} × 3^{max(0,1,0)} × 5^{max(0,0,1)} = 2^3 × 3^1 × 5^1 = 8 × 3 × 5 = 120.

  3. Final Answer:

    LCM(8,12,20) = 120 → Option A.

  4. Quick Check:

    120 ÷ 8 = 15, 120 ÷ 12 = 10, 120 ÷ 20 = 6 → all integers and 120 is the least such number. ✅
Hint: For multiple numbers, take max prime exponents across all numbers.
Common Mistakes: Computing pairwise LCM incorrectly or missing a prime factor (like 5 here).

Mock Test

Ready for a challenge?

Take a 10-minute AI-powered test with 10 questions (Easy-Medium-Hard mix) and get instant SWOT analysis of your performance!

10 Questions
5 Minutes