7. Highest Common Factors and Least Common Multiples

1. Understanding the Basics

1.1 Highest Common Factor (HCF)

The HCF (or GCF – Greatest Common Factor) of two or more numbers is the largest number that divides all the numbers without leaving a remainder.

Example 1: Find the HCF of $12$ and $18$.

Solution:
Factors of $12$: $1, 2, 3, 4, 6, 12$.
Factors of $18$: $1, 2, 3, 6, 9, 18$.
Common factors: $1, 2, 3, 6$.
HCF: $6$.

1.2 Least Common Multiple (LCM)

The LCM of two or more numbers is the smallest number that is divisible by all the given numbers.

Example 2: Find the LCM of $4$ and $6$.

Solution:
Multiples of $4$: $4, 8, 12, 16, 20, \dots$.
Multiples of $6$: $6, 12, 18, 24, 30, \dots$.
Common multiples: $12, 24, \dots$.
LCM: $12$.

2. Methods to Find HCF and LCM

2.1 Prime Factorization Method

1. Write each number as a product of prime factors.
2. For HCF, take the smallest power of common prime factors.
3. For LCM, take the highest power of all prime factors.

Example 3: Find the HCF and LCM of $20$ and $30$ using prime factorization.

Solution:
Prime factorization of $20 = 2^2 \times 5$.
Prime factorization of $30 = 2 \times 3 \times 5$.

• HCF: $2^1 \times 5 = 10$.
• LCM: $2^2 \times 3 \times 5 = 60$.

2.2 Division Method (for HCF)

1. Divide the larger number by the smaller number.
2. Use the remainder as the new divisor and repeat until the remainder is $0$.
3. The last divisor is the HCF.

Example 4: Find the HCF of $48$ and $18$ using the division method.

Solution:

$$48 \div 18 = 2 \, \text{remainder } 12 \quad \text{(Step 1)}$$ $$18 \div 12 = 1 \, \text{remainder } 6 \quad \text{(Step 2)}$$ $$12 \div 6 = 2 \, \text{remainder } 0 \quad \text{(Step 3)}$$

HCF: $6$.

2.3 Common Multiples Method (for LCM)

1. List multiples of each number.
2. Identify the smallest common multiple.

3. Relationship Between HCF and LCM

For two numbers $a$ and $b$:

$$\text{HCF}(a, b) \times \text{LCM}(a, b) = a \times b.$$

Example 5: Verify the relationship for $12$ and $18$.

Solution:
HCF: $6$, LCM: $36$.

$$\text{HCF} \times \text{LCM} = 6 \times 36 = 216.$$ $$a \times b = 12 \times 18 = 216.$$

The relationship holds true.

4. Advanced Applications

4.1 Word Problems

1. Problems involving equal groupings often use HCF.
2. Problems involving periodic events or synchronization use LCM.

Example 6: Two bells ring every $4$ minutes and $6$ minutes. When will they ring together again?

Solution:
Find the LCM of $4$ and $6$.

$$\text{LCM} = 12 \, \text{minutes}.$$

The bells will ring together after $12$ minutes.

Example 7: A farmer has $72$ apples, $96$ oranges, and $120$ bananas. He wants to pack them into boxes with an equal number of each fruit. What is the largest number of fruits per box?

Solution:
Find the HCF of $72$, $96$, and $120$.

$$\text{HCF} = 24.$$

Each box will have $24$ fruits.

5. Complex Scenarios

Example 8: Three cyclists start together and cycle $60$, $75$, and $90$ km in a day. When will they meet again?

Solution:
Find the LCM of $60$, $75$, and $90$.

$$\text{Prime factorization: } 60 = 2^2 \times 3 \times 5, \, 75 = 3 \times 5^2, \, 90 = 2 \times 3^2 \times 5.$$ $$\text{LCM} = 2^2 \times 3^2 \times 5^2 = 900 \, \text{km}.$$

They will meet again after $900$ km.

6. Practice Questions

1. Find the HCF of $24$ and $36$.

Solution:
Using prime factorization:

$$24 = 2^3 \times 3, \quad 36 = 2^2 \times 3^2.$$

Common prime factors: $2^2 \times 3 = 12$.
HCF = 12.

2. Find the LCM of $8$ and $12$.

Solution:
Using prime factorization:

$$8 = 2^3, \quad 12 = 2^2 \times 3.$$

Take the highest powers of all prime factors:

$$\text{LCM} = 2^3 \times 3 = 24.$$

LCM = 24.

3. Determine the HCF and LCM of $15$ and $20$.

Solution:
Prime factorizations:

$$15 = 3 \times 5, \quad 20 = 2^2 \times 5.$$

• HCF: Common prime factor is $5$.
• LCM: $2^2 \times 3 \times 5 = 60$.

HCF = 5, LCM = 60.

4. Prove the relationship between HCF and LCM for $18$ and $24$.

Solution:
Prime factorizations:

$$18 = 2 \times 3^2, \quad 24 = 2^3 \times 3.$$

• HCF: $2^1 \times 3^1 = 6$.
• LCM: $2^3 \times 3^2 = 72$.
  Verify the relationship:

$$\text{HCF} \times \text{LCM} = 6 \times 72 = 432, \quad 18 \times 24 = 432.$$

The relationship holds true.

5. Two trains run every $18$ and $24$ minutes. When will they next run together?

Solution:
Find the LCM of $18$ and $24$.

$$18 = 2 \times 3^2, \quad 24 = 2^3 \times 3.$$ $$\text{LCM} = 2^3 \times 3^2 = 72.$$

The trains will next run together after $72$ minutes.

6. Pack $48$, $60$, and $72$ items into equal boxes. What is the largest number of items per box?

Solution:
Find the HCF of $48$, $60$, and $72$.

$$48 = 2^4 \times 3, \quad 60 = 2^2 \times 3 \times 5, \quad 72 = 2^3 \times 3^2.$$

Common prime factors: $2^2 \times 3 = 12$.
HCF = 12.

Each box will have $12$ items.

7. Find the LCM of $14$, $28$, and $35$.

Solution:
Prime factorizations:

$$14 = 2 \times 7, \quad 28 = 2^2 \times 7, \quad 35 = 5 \times 7.$$

Take the highest powers of all primes:

$$\text{LCM} = 2^2 \times 5 \times 7 = 140.$$

LCM = 140.

8. A clock chimes every $15$ minutes and another every $20$ minutes. When will they chime together?

Solution:
Find the LCM of $15$ and $20$.

$$15 = 3 \times 5, \quad 20 = 2^2 \times 5.$$ $$\text{LCM} = 2^2 \times 3 \times 5 = 60.$$

The clocks will chime together after $60$ minutes.

9. Verify the HCF and LCM relationship for $25$ and $30$.

Solution:
Prime factorizations:

$$25 = 5^2, \quad 30 = 2 \times 3 \times 5.$$

• HCF: $5$.
• LCM: $2 \times 3 \times 5^2 = 150$.
  Verify:

$$\text{HCF} \times \text{LCM} = 5 \times 150 = 750, \quad 25 \times 30 = 750.$$

The relationship holds true.

10. What is the smallest number divisible by $3, 4,$ and $6$?

Solution:
Find the LCM of $3$, $4$, and $6$.

$$3 = 3, \quad 4 = 2^2, \quad 6 = 2 \times 3.$$ $$\text{LCM} = 2^2 \times 3 = 12.$$

Smallest number = 12.

11. Find the largest number that divides $100, 150,$ and $200$ without leaving a remainder.

Solution:
Find the HCF of $100$, $150$, and $200$.

$$100 = 2^2 \times 5^2, \quad 150 = 2 \times 3 \times 5^2, \quad 200 = 2^3 \times 5^2.$$

Common prime factors: $2^1 \times 5^2 = 50$.
HCF = 50.

12. Find the LCM of $5$, $10$, and $15$.

Solution:
Prime factorizations:

$$5 = 5, \quad 10 = 2 \times 5, \quad 15 = 3 \times 5.$$ $$\text{LCM} = 2 \times 3 \times 5 = 30.$$

LCM = 30.

13. If $\text{HCF}(x, 40) = 8$ and $\text{LCM}(x, 40) = 120$, find $x$.

Solution:
Using the relationship:

$$\text{HCF} \times \text{LCM} = x \times 40.$$ $$8 \times 120 = x \times 40.$$ $$x = \frac{960}{40} = 24.$$

$x = 24$.

14. The product of two numbers is $180$. If their HCF is $6$, find their LCM.

Solution:
Using the relationship:

$$\text{HCF} \times \text{LCM} = \text{Product of numbers}.$$ $$6 \times \text{LCM} = 180.$$ $$\text{LCM} = \frac{180}{6} = 30.$$

LCM = 30.

15. A boy skips every $6$ steps and a girl every $9$ steps. When will they skip together?

Solution:
Find the LCM of $6$ and $9$.

$$6 = 2 \times 3, \quad 9 = 3^2.$$ $$\text{LCM} = 2 \times 3^2 = 18.$$

They will skip together after $18$ steps.

16. Verify the HCF of $72$ and $90$ using prime factorization.

Solution:

$$72 = 2^3 \times 3^2, \quad 90 = 2 \times 3^2 \times 5.$$

Common prime factors: $2 \times 3^2 = 18$.
HCF = 18.

17. Find the smallest multiple of $12$ and $18$ greater than $100$.

Solution:
Find the LCM of $12$ and $18$:

$$12 = 2^2 \times 3, \quad 18 = 2 \times 3^2.$$ $$\text{LCM} = 2^2 \times 3^2 = 36.$$

Multiples of $36$: $36, 72, 108, \dots$.
The smallest multiple greater than $100$ is $108$.
Answer: $108$.

18. How many numbers less than $50$ are multiples of $4$ and $6$?

Solution:
Find the LCM of $4$ and $6$:

$$\text{LCM} = 12.$$

Multiples of $12$ less than $50$: $12, 24, 36, 48$.
Answer: $4$ numbers.

19. Pack $30, 45,$ and $75$ chocolates into equal boxes. What is the largest number per box?

Solution:
Find the HCF of $30$, $45$, and $75$:

$$30 = 2 \times 3 \times 5, \quad 45 = 3^2 \times 5, \quad 75 = 3 \times 5^2.$$

Common prime factors: $3 \times 5 = 15$.
Answer: $15$ chocolates per box.

20. Two runners complete a lap every $8$ and $12$ minutes. When will they meet at the starting point?

Solution:
Find the LCM of $8$ and $12$:

$$\text{LCM} = 2^3 \times 3 = 24.$$

They will meet at the starting point after $24$ minutes.