0
0

Factors & Multiples (HCF & LCM)

Introduction

Factors और multiples, fractions को simplify करने, divisibility problems solve करने और repeating events को schedule करने में बहुत काम आते हैं। HCF / GCD और LCM जल्दी निकाल पाना aptitude tests और competitive exams में काफी time बचाता है।

Pattern: Factors & Multiples (HCF & LCM)

Pattern

HCF निकालने के लिए common prime powers के minimum exponents लें; LCM के लिए सभी prime powers के maximum exponents लें। Fast calculation के लिए Euclid’s algorithm और product identity का उपयोग करें।

  • Factor: d, n का factor है अगर n ÷ d एक integer हो।
  • Multiple: m, n का multiple है अगर m = n × k (किसी integer k के लिए)।
  • Prime factorization: Numbers को primes के product के रूप में लिखें:
    a = ∏ p_i^{α_i}, b = ∏ p_i^{β_i} (prime absent हो तो exponent 0 लें)।
  • 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). Remainder 0 होने तक repeat करें; last non-zero remainder ही 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

84 और 108 का HCF (GCD) और LCM निकालें।

Solution

  1. Step 1: Prime factorization

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

  2. Step 2: HCF (min exponents)

    HCF(84,108) = 2min(2,2) × 3min(1,3) × 7min(1,0) = 2² × 3¹ × 7⁰ = 4 × 3 × 1 = 12.

  3. Step 3: LCM (max exponents)

    LCM(84,108) = 2max(2,2) × 3max(1,3) × 7max(1,0) = 2² × 3³ × 7¹ = 4 × 27 × 7 = 756.

  4. Step 4: Product identity से verify करें

    84 × 108 = 9072. HCF × LCM = 12 × 756 = 9072 → बिल्कुल match। ✅

  5. Final Answer:

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

  6. Quick Check:

    756 ÷ 84 = 9 (integer) और 756 ÷ 108 = 7 (integer)। 12 दोनों numbers को divide करता है → HCF सही। Product identity भी सही। ✅

Quick Variations

1. बड़े numbers के लिए Euclidean algorithm use करें: gcd(108,84) → gcd(84,24) → gcd(24,12) → gcd(12,0) = 12.

2. तीन numbers के लिए stepwise method: GCD(a,b,c)=GCD(GCD(a,b),c) और LCM के लिए भी वैसा ही।

3. अगर numbers co-prime हों (GCD = 1), तो LCM = उनका product।

Trick to Always Use

  • Step 1 → GCD के लिए Euclidean algorithm सबसे fast है।
  • Step 2 → LCM जल्दी निकालने के लिए formula LCM = |a × b| / GCD(a,b) use करें।
  • Step 3 → छोटे numbers के लिए prime factorization और min/max exponents वाला rule clear और reliable है।
  • Step 4 → कई numbers हों तो pairwise method use करें।

Summary

Summary

  • HCF prime powers के minimum exponents से या Euclid algorithm से निकालें।
  • LCM prime powers के maximum exponents से या formula LCM = |a × b| / GCD से निकालें।
  • HCF × LCM = |a × b| identity हमेशा सही होती है।
  • कई numbers के लिए operations को stepwise apply करें।

Example याद रखें:
84 और 108 के लिए HCF = 12 और LCM = 756 क्योंकि min/max exponents से exact values मिलती हैं, और 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