LCM and HCF

Introduction to LCM and HCF

In mathematics, the Least Common Multiple (LCM) and Highest Common Factor (HCF), also known as the Greatest Common Divisor (GCD), are fundamental concepts related to integers. Understanding these concepts is crucial for solving various problems in arithmetic, number theory, and algebra. They are particularly useful in simplifying fractions, solving problems involving ratios and proportions, and in many real-world scenarios.

Highest Common Factor (HCF) / Greatest Common Divisor (GCD)

The HCF of two or more integers is the largest positive integer that divides each of the integers without leaving a remainder. In simpler terms, it's the biggest number that is a factor of all the given numbers.

Methods to find HCF:

1. Prime Factorization Method: This method involves finding the prime factors of each number and then identifying the common prime factors. The HCF is the product of these common prime factors raised to the lowest power they appear in any of the factorizations.

Example: Find the HCF of 12 and 18. Prime factorization of 12: 2 × 2 × 3 = 2² × 3¹ Prime factorization of 18: 2 × 3 × 3 = 2¹ × 3² The common prime factors are 2 and 3. The lowest power of 2 is 2¹ and the lowest power of 3 is 3¹. HCF(12, 18) = 2¹ × 3¹ = 6.

2. Division Method (Euclidean Algorithm): This is a more efficient method, especially for larger numbers. It is based on the principle that the greatest common divisor of two numbers does not change if the larger number is replaced by its difference with the smaller number. This process is repeated until one of the numbers becomes zero, and the other non-zero number is the HCF. A more common form of the Euclidean algorithm uses division with remainder.

Algorithm: Let a and b be two non-negative integers, with a ≥ b. If b = 0, then HCF(a, b) = a. If b ≠ 0, then HCF(a, b) = HCF(b, a mod b), where 'a mod b' is the remainder when a is divided by b.

Example: Find the HCF of 48 and 18. Step 1: Divide 48 by 18. 48 = 18 × 2 + 12. The remainder is 12. Step 2: Now find HCF(18, 12). Divide 18 by 12. 18 = 12 × 1 + 6. The remainder is 6. Step 3: Now find HCF(12, 6). Divide 12 by 6. 12 = 6 × 2 + 0. The remainder is 0. Since the remainder is 0, the HCF is the last non-zero remainder, which is 6. HCF(48, 18) = 6.

3. Listing Factors Method: List all the factors (divisors) of each number. The HCF is the largest number that appears in all the lists. This method is suitable only for small numbers.

Example: Find the HCF of 12 and 18. Factors of 12: 1, 2, 3, 4, 6, 12 Factors of 18: 1, 2, 3, 6, 9, 18 Common factors: 1, 2, 3, 6 The highest common factor is 6.

Least Common Multiple (LCM)

The LCM of two or more integers is the smallest positive integer that is a multiple of each of the integers. In simpler terms, it's the smallest number that all the given numbers can divide into evenly.

Methods to find LCM:

1. Prime Factorization Method: Find the prime factorization of each number. The LCM is the product of all the prime factors that appear in any of the factorizations, each raised to the highest power it appears in any of the factorizations.

Example: Find the LCM of 12 and 18. Prime factorization of 12: 2 × 2 × 3 = 2² × 3¹ Prime factorization of 18: 2 × 3 × 3 = 2¹ × 3² The prime factors involved are 2 and 3. The highest power of 2 is 2² and the highest power of 3 is 3². LCM(12, 18) = 2² × 3² = 4 × 9 = 36.

2. Division Method: Write the numbers in a row. Divide them by a common prime factor. Write the quotients below. If a number is not divisible, bring it down as it is. Repeat the process until all the numbers become 1. The LCM is the product of the divisors.

Example: Find the LCM of 12 and 18. ``` 2 | 12, 18 --|------- 3 | 6, 9 --|------- | 2, 3 ``` Now, 2 and 3 are prime numbers, so we divide by them. ``` 2 | 12, 18 --|------- 3 | 6, 9 --|------- 2 | 2, 3 --|------- 3 | 1, 3 --|------- | 1, 1 ``` LCM = 2 × 3 × 2 × 3 = 36.

3. Listing Multiples Method: List the multiples of each number until a common multiple is found. The smallest common multiple is the LCM. This method is only practical for small numbers.

Example: Find the LCM of 12 and 18. Multiples of 12: 12, 24, 36, 48, 60, ... Multiples of 18: 18, 36, 54, 72, ... The smallest common multiple is 36.

Relationship between HCF and LCM

For any two positive integers 'a' and 'b', there is a fundamental relationship between their HCF and LCM: HCF(a, b) × LCM(a, b) = a × b

This relationship is extremely useful for solving problems. If you know any three of the four values (a, b, HCF, LCM), you can find the fourth.

Example: The HCF of two numbers is 12 and their LCM is 72. If one of the numbers is 36, find the other number. Let the two numbers be 'a' and 'b'. We are given: HCF(a, b) = 12 LCM(a, b) = 72 a = 36 We need to find 'b'. Using the formula: HCF × LCM = a × b 12 × 72 = 36 × b b = (12 × 72) / 36 b = 12 × (72 / 36) b = 12 × 2 b = 24. So, the other number is 24.

Note: This formula HCF × LCM = a × b is valid ONLY for two numbers. For three or more numbers, there isn't a simple direct formula like this. However, we can find the HCF and LCM of three numbers using the prime factorization or division method extended to three numbers.

Applications of HCF and LCM

HCF and LCM concepts appear in various types of problems, especially in competitive exams. Here are some common scenarios:

1. Problems involving finding the largest/smallest number:

Largest number that divides A, B, C exactly: This is the HCF of A, B, and C. Smallest number that is exactly divisible by A, B, C: This is the LCM of A, B, and C.

2. Problems involving remainders:

Largest number that divides A, B, C leaving remainder R in each case: First, subtract R from each number (A-R, B-R, C-R). Then, find the HCF of these new numbers. Largest number that divides A, B, C leaving remainders R1, R2, R3 respectively: First, subtract the remainder from the respective number (A-R1, B-R2, C-R3). Then, find the HCF of these new numbers. Smallest number which when divided by A, B, C leaves remainder R in each case: First, find the LCM of A, B, and C. Then, add R to the LCM. (LCM(A, B, C) + R). Smallest number which when divided by A, B, C leaves remainders R1, R2, R3 respectively: This type often has a pattern. If (A - R1) = (B - R2) = (C - R3) = K (a constant), then the required number is LCM(A, B, C) - K.

Example: Find the largest number that divides 130, 305, and 355 exactly. We need to find HCF(130, 305, 355). Prime factorization of 130: 2 × 5 × 13 Prime factorization of 305: 5 × 61 Prime factorization of 355: 5 × 71 The only common prime factor is 5. HCF(130, 305, 355) = 5. The largest number is 5.

Example: Find the smallest number which when divided by 12, 15, and 18 leaves a remainder of 5 in each case. First, find LCM(12, 15, 18). 12 = 2² × 3 15 = 3 × 5 18 = 2 × 3² LCM = 2² × 3² × 5 = 4 × 9 × 5 = 180. The required number is LCM + Remainder = 180 + 5 = 185.

Example: Find the smallest number which when divided by 10, 12, and 15 leaves remainders 7, 9, and 12 respectively. Check the difference between the divisor and the remainder: 10 - 7 = 3 12 - 9 = 3 15 - 12 = 3 The difference is constant (K=3). Find LCM(10, 12, 15). 10 = 2 × 5 12 = 2² × 3 15 = 3 × 5 LCM = 2² × 3 × 5 = 4 × 3 × 5 = 60. The required number is LCM - K = 60 - 3 = 57.

3. Problems involving bells or signals:

If bells ring at intervals of 'a', 'b', and 'c' seconds, they will all ring together again after LCM(a, b, c) seconds. This is because we are looking for the smallest time that is a multiple of all the given intervals.

Example: Three bells ring at intervals of 12 minutes, 15 minutes, and 18 minutes. If they all start ringing together, after how much time will they next ring together? We need to find LCM(12, 15, 18). 12 = 2² × 3 15 = 3 × 5 18 = 2 × 3² LCM = 2² × 3² × 5 = 4 × 9 × 5 = 180 minutes. They will next ring together after 180 minutes (or 3 hours).

4. Problems involving arranging objects in groups:

If you want to arrange a certain number of items (e.g., students, fruits) into equal groups of size 'x', 'y', or 'z', you are looking for a number that is a multiple of x, y, and z. The smallest such number is the LCM.

Example: What is the smallest number of apples that can be arranged in groups of 6, 8, or 10? This is asking for the LCM of 6, 8, and 10. 6 = 2 × 3 8 = 2³ 10 = 2 × 5 LCM = 2³ × 3 × 5 = 8 × 3 × 5 = 120 apples.

Practice Problems

1. Find the HCF of 252, 396, and 504.

2. Find the LCM of 15, 25, and 35.

3. The HCF of two numbers is 16 and their LCM is 384. If one number is 64, find the other.

4. Find the largest number which divides 62, 132, and 157 leaving the same remainder in each case.

5. Find the smallest number which when divided by 8, 12, and 16 leaves a remainder of 3 in each case.

6. Four bells toll at intervals of 30 minutes, 45 minutes, 60 minutes, and 75 minutes respectively. If they start tolling together, after how long will they next toll together?

7. Find the HCF of 7/9, 14/15, and 21/10.

8. Find the LCM of 4/5, 6/7, and 8/9.

9. Find the smallest number of 5 digits that is exactly divisible by 12, 15, 18, and 24.

10. Find the greatest number of 4 digits which when divided by 6, 7, and 8 leaves remainders 3, 4, and 5 respectively.