HCF and LCM

Factors and Multiples

• A factor of a number divides it exactly (no remainder).

  • Example: 3 is a factor of 12.

• A multiple of a number is obtained by multiplying it by an integer.

  • Example: 24 is a multiple of 6.

---

HCF (Highest Common Factor)

HCF of two or more numbers is the greatest number that divides all of them exactly.

$$\text{HCF}(a, b) = \max\{k \mid k \mid a \text{ and } k \mid b\}$$

Use Case: Sharing, cutting into maximum equal parts, minimizing length or time.

---

LCM (Least Common Multiple)

LCM of two or more numbers is the smallest number that is a multiple of all of them.

$$\text{LCM}(a, b) = \min\{m \mid a \mid m \text{ and } b \mid m\}$$

Use Case: Scheduling, synchronization, recurring cycles, time intervals.

---

Prime Factorization

Breaking a number into its constituent prime numbers.

$$\text{Example: } 60 = 2^2 \times 3 \times 5$$

Use: Efficiently compute HCF and LCM.

---

Key Formulas and Shortcuts

Relation Between HCF and LCM

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

This is valid only for two numbers.

---

HCF Using Prime Factorization

• Factorize each number.
• Take common primes with the lowest powers.

Example:
36 = $2^2 \times 3^2$
60 = $2^2 \times 3 \times 5$

$$\text{HCF}(36, 60) = 2^2 \times 3 = 12$$

---

LCM Using Prime Factorization

• Factorize each number.
• Take all primes with the highest powers.

$$\text{LCM}(36, 60) = 2^2 \times 3^2 \times 5 = 180$$

---

Shortcut: Euclidean Algorithm for HCF (of two numbers)

Given two numbers $a > b$:

$$\text{HCF}(a, b) = \text{HCF}(b, a \bmod b)$$

Repeat until remainder is 0.

Example:
Find HCF(91, 65)

$$91 \mod 65 = 26 \Rightarrow \text{HCF}(65, 26) \\ 65 \mod 26 = 13 \Rightarrow \text{HCF}(26, 13) \\ 26 \mod 13 = 0 \Rightarrow \text{HCF} = 13$$

---

HCF and LCM of Fractions

When dealing with fractions, the concepts of HCF and LCM are extended based on their numerators and denominators.

---

HCF of Fractions

To find the HCF of a set of fractions:

$$\text{HCF} = \frac{\text{HCF of numerators}}{\text{LCM of denominators}}$$

Example: Find the HCF of $\frac{4}{9}, \frac{8}{15}, \frac{12}{25}$

• Numerators: HCF(4, 8, 12) = 4
• Denominators: LCM(9, 15, 25) = 225

$$\text{HCF} = \frac{4}{225}$$

---

LCM of Fractions

To find the LCM of a set of fractions:

$$\text{LCM} = \frac{\text{LCM of numerators}}{\text{HCF of denominators}}$$

Example: Find the LCM of $\frac{2}{3}, \frac{5}{6}, \frac{4}{9}$

• Numerators: LCM(2, 5, 4) = 20
• Denominators: HCF(3, 6, 9) = 3

$$\text{LCM} = \frac{20}{3}$$

---

Conceptual Tips and Common Mistakes

---

Factor Trees and Visual Aid

Example: Factor tree for 84

        84
       /  \
      2    42
          /  \
         2    21
              / \
             3   7
→ 84 = 2^2 × 3 × 7

Visualizing through factor trees aids quick mental prime factorization.

---

Examples

Example 1:

Find HCF and LCM of 36 and 60.

Prime Factorizations:
36 = $2^2 \times 3^2$
60 = $2^2 \times 3 \times 5$

$$\text{HCF} = 2^2 \times 3 = 12 \\ \text{LCM} = 2^2 \times 3^2 \times 5 = 180$$

---

Example 2:

What is the HCF of 120, 160, and 200?

Factorizations:

• 120 = $2^3 \times 3 \times 5$
• 160 = $2^5 \times 5$
• 200 = $2^3 \times 5^2$

HCF: $2^3 \times 5 = 40$

---

Example 3:

Two alarm clocks ring every 20 min and 30 min. If they ring together at 9:00 AM, when will they next ring together?

$$\text{LCM}(20, 30) = 60 \text{ minutes} \Rightarrow \text{Answer: } 10:00 AM$$

---

Applications of HCF and LCM

---

Special Cases

• If two numbers are co-prime, HCF = 1 and

  $$\text{LCM} = a \times b$$

• If one number divides another:

  $$\text{HCF} = \text{smaller}, \quad \text{LCM} = \text{larger}$$