LCM & HCF

Core Formula

HCF (Highest Common Factor) / GCD (Greatest Common Divisor): The largest positive integer that divides two or more integers without leaving a remainder. LCM (Least Common Multiple): The smallest positive integer that is a multiple of two or more integers.

Methods to Calculate HCF & LCM:

1. Prime Factorization Method:
   • Find the prime factors of each number.
   • HCF: Product of the common prime factors, each raised to the lowest power.
   • LCM: Product of all prime factors (common and uncommon), each raised to the highest power.
2. Division Method (for HCF): Divide the larger number by the smaller number. Then divide the divisor by the remainder. Continue until the remainder is 0. The last divisor is the HCF.
3. Division Method (for LCM): Write the numbers in a row. Divide by a prime number that divides at least two numbers. Bring down numbers not divisible. Repeat until no two numbers are divisible by a common prime. Multiply all divisors and the remaining numbers.

Crucial Relationship for Two Numbers: Product of two numbers = HCF × LCM

For Fractions:

• HCF of fractions = HCF of numerators / LCM of denominators
• LCM of fractions = LCM of numerators / HCF of denominators

Worked Example 1

Problem: Find the HCF and LCM of 24 and 36.

Solution: Prime Factorization Method:

• 24 = 2 × 2 × 2 × 3 = 2³ × 3¹
• 36 = 2 × 2 × 3 × 3 = 2² × 3²
• HCF: Common factors with lowest powers: 2² × 3¹ = 4 × 3 = 12
• LCM: All factors with highest powers: 2³ × 3² = 8 × 9 = 72

Division Method (for HCF):

• 36 ÷ 24 = 1 remainder 12
• 24 ÷ 12 = 2 remainder 0
• Last divisor is 12. So, HCF = 12.

Division Method (for LCM):

2 | 24, 36
2 | 12, 18
3 |  6,  9
  |  2,  3

• LCM = 2 × 2 × 3 × 2 × 3 = 72

Worked Example 2

Problem: Find the HCF and LCM of 15, 25, and 40.

Solution: Prime Factorization Method:

• 15 = 3 × 5
• 25 = 5 × 5 = 5²
• 40 = 2 × 2 × 2 × 5 = 2³ × 5
• HCF: Common factors with lowest powers: 5¹ = 5
• LCM: All factors with highest powers: 2³ × 3¹ × 5² = 8 × 3 × 25 = 600

Division Method (for HCF of three numbers):

• First find HCF of any two, say 15 and 25.
  • 25 ÷ 15 = 1 remainder 10
  • 15 ÷ 10 = 1 remainder 5
  • 10 ÷ 5 = 2 remainder 0. HCF(15, 25) = 5.
• Now find HCF of this result (5) and the third number (40).
  • 40 ÷ 5 = 8 remainder 0. HCF(5, 40) = 5.
• So, HCF(15, 25, 40) = 5.

Division Method (for LCM of three numbers):

5 | 15, 25, 40
  |  3,  5,  8  (No common prime factor for any two)

• LCM = 5 × 3 × 5 × 8 = 600

Shortcuts & Tricks

1. Product of Two Numbers: If HCF and LCM of two numbers are given, and one number is known, use Number1 × Number2 = HCF × LCM to find the other number quickly. (Refer to Q3 in related questions).
2. HCF by Difference Method: The HCF of two numbers must divide their difference. For multiple numbers, find the HCF of the differences between consecutive numbers. This can quickly narrow down options.
   • Example: HCF of 24, 36. Difference = 12. HCF must divide 12. (Possible HCFs: 1, 2, 3, 4, 6, 12). Since 12 divides both 24 and 36, HCF is 12.
3. LCM by Inspection: For smaller numbers, start with the largest number and check its multiples. The first multiple that is divisible by all other numbers is the LCM.
   • Example: LCM of 4, 6, 10. Largest is 10. Multiples of 10: 10 (not div by 4, 6), 20 (not div by 6), 30 (not div by 4), 40 (not div by 6), 50 (not div by 4, 6), 60 (div by 4, 6, 10). So LCM = 60. (Refer to Q2 in related questions).
4. For Numbers with Exponents: HCF is the product of common prime bases raised to the minimum power. LCM is the product of all prime bases (common and uncommon) raised to the maximum power.

Common Mistakes

1. Confusing HCF and LCM: Students often mix up the definitions or the rules for prime factorization (e.g., using highest power for HCF or lowest for LCM).
2. Incorrect Prime Factorization: Errors in breaking down numbers into their prime factors, leading to incorrect HCF/LCM.
3. Ignoring the 'Product' Formula: Failing to use Number1 × Number2 = HCF × LCM when applicable, especially for problems where one number is unknown.
4. Errors with Fractions: Incorrectly applying the HCF/LCM rules for numerators and denominators (e.g., taking LCM of numerators for HCF of fractions).

Core Formula

LCM (Least Common Multiple) is the smallest positive integer that is divisible by each of the given integers. HCF (Highest Common Factor) or GCD (Greatest Common Divisor) is the largest positive integer that divides each of the given integers without leaving a remainder.

Fundamental Relation: Product of two numbers = LCM(a, b) * HCF(a, b)

For Fractions: LCM(a/b, c/d) = LCM(a, c) / HCF(b, d) HCF(a/b, c/d) = HCF(a, c) / LCM(b, d)

Worked Example 1

Problem: Three bells ring at intervals of 12, 15, and 18 minutes respectively. If they start ringing together at 9 AM, when will they next ring together?

Solution: To find when they will next ring together, we need to find the LCM of their ringing intervals.

1. Prime factorize each number: 12 = 2^2 * 3 15 = 3 * 5 18 = 2 * 3^2
2. Calculate LCM by taking the highest power of all prime factors: LCM(12, 15, 18) = 2^2 * 3^2 * 5 = 4 * 9 * 5 = 180
3. The bells will ring together after 180 minutes.
4. Convert minutes to hours: 180 minutes = 3 hours.
5. If they started at 9 AM, they will next ring together at 9 AM + 3 hours = 12 PM.

Worked Example 2

Problem: A milkman has 75 litres of milk in one can and 45 litres in another. What is the maximum capacity of a container that can measure milk exactly from both cans?

Solution: To find the maximum capacity, we need to find the HCF of the quantities of milk in the cans.

1. Prime factorize each number: 75 = 3 * 5^2 45 = 3^2 * 5
2. Calculate HCF by taking the lowest power of common prime factors: HCF(75, 45) = 3^1 * 5^1 = 15
3. The maximum capacity of the container is 15 litres.

Shortcuts & Tricks

1. Remainder Problems (LCM):
   • Same Remainder: If a number leaves the same remainder r when divided by x, y, z, the number is LCM(x, y, z) + r.
   • Same Difference: If a number leaves remainders r1, r2, r3 when divided by x, y, z respectively, and (x-r1) = (y-r2) = (z-r3) = k (a common difference), the number is LCM(x, y, z) - k.
2. Remainder Problems (HCF):
   • Same Remainder: If a number divides x, y, z leaving the same remainder r, the HCF of (x-r), (y-r), (z-r) is the required number. Alternatively, the HCF of |x-y|, |y-z|, |z-x| is the required number.
3. Euclidean Algorithm for HCF: For larger numbers, repeatedly apply HCF(a, b) = HCF(b, a mod b) until the remainder is 0. The last non-zero divisor is the HCF.
4. Option Elimination: In multiple-choice questions, use the properties of LCM/HCF and remainders to quickly eliminate incorrect options.

Common Mistakes

1. Confusing LCM and HCF: Students often use LCM where HCF is required (e.g., finding the 'least' number of tiles for a floor, which is HCF to find the largest tile size, then LCM for number of tiles) or vice-versa. Keywords like 'least', 'minimum', 'together' usually imply LCM. Keywords like 'greatest', 'maximum', 'largest', 'divide exactly' usually imply HCF.
2. Incorrect Remainder Handling: For remainder problems, incorrectly adding/subtracting the remainder or common difference. Always double-check if it's LCM + r or LCM - k.
3. Calculation Errors: Mistakes in prime factorization or arithmetic, especially with larger numbers. Practice mental math and quick factorization.
4. Ignoring the 'Product of two numbers' rule: For problems involving two numbers where LCM and HCF are given, this formula is a huge time-saver and often overlooked.