HCF and LCM

Highest Common Factor (HCF): Definition and Methods

---

Defining the Highest Common Factor (HCF)

The Highest Common Factor (HCF) of two or more integers is the largest positive integer that divides each of the given integers without leaving a remainder. It is also widely known as the Greatest Common Divisor (GCD). The terms HCF and GCD are used interchangeably, referring to the same concept.

To understand HCF, let's break it down:

• Factors (or Divisors): As defined previously, a factor of an integer is a number that divides it exactly. For example, the positive factors of 12 are 1, 2, 3, 4, 6, and 12.
• Common Factors: For a set of two or more integers, the common factors are the factors that are shared by all the numbers in the set. For example, the positive factors of 12 are {1, 2, 3, 4, 6, 12}, and the positive factors of 18 are {1, 2, 3, 6, 9, 18}. The factors common to both 12 and 18 are {1, 2, 3, 6}.
• Highest (or Greatest) Common Factor: Among the common factors, the HCF is the largest one. In the example of 12 and 18, the common factors are {1, 2, 3, 6}. The largest number in this set is 6. Therefore, the HCF of 12 and 18 is 6. HCF(12, 18) = 6.

Example: Find the HCF of $30$ and $45$.

• Positive factors of $30$: $1, 2, 3, 5, 6, 10, 15, 30$.
• Positive factors of $45$: $1, 3, 5, 9, 15, 45$.

The common factors of $30$ and $45$ are the numbers appearing in both lists: $1, 3, 5, 15$.

The largest among these common factors is $15$.

Therefore, HCF$(30, 45) = 15$.

---

Methods for Calculating HCF

Several methods can be used to calculate the HCF of two or more integers. The choice of method depends on the numbers involved and personal preference. The methods are generally applied to positive integers, as the HCF of negative integers is the same as the HCF of their absolute values.

Method 1: Listing Common Factors

This is the simplest method conceptually, especially for small numbers. You list all positive factors for each number and then find the largest factor that is present in all lists.

Steps:

1. List all positive factors for the first number.
2. List all positive factors for the second number.
3. Repeat for any additional numbers.
4. Identify the set of factors that are common to all the lists.
5. The largest number in the set of common factors is the HCF.

Answer:

While easy to understand, this method becomes impractical for large numbers where listing all factors is tedious.

Method 2: Prime Factorisation Method

This method uses the unique prime factorization of each number (guaranteed by the Fundamental Theorem of Arithmetic) to find the HCF. It's more efficient than listing factors for larger numbers.

Steps:

1. Find the prime factorization of each of the given numbers. Use methods like the division method or factor tree.
2. Write the prime factorization of each number, usually in exponential form (e.g., $p_1^{e_1} \times p_2^{e_2} \times \ldots$).
3. Identify all the prime numbers that are common factors in *all* the prime factorizations.
4. For each common prime factor, select the lowest exponent (power) to which it is raised across all the factorizations. If a prime factor is common but appears with different powers, choose the smallest power. If it appears in one factorization but not another, it's not a common factor.
5. Multiply these selected lowest powers of the common prime factors. The product is the HCF. If there are no common prime factors (other than the implicit $p^0=1$), the HCF is 1.

Answer:

Method 3: Long Division Method (Euclidean Algorithm)

The Euclidean Algorithm is one of the oldest known algorithms and is a very efficient method for finding the HCF of two positive integers, especially large ones. It is based on the property that the HCF of two numbers remains the same if the larger number is replaced by the remainder obtained when the larger number is divided by the smaller number.

The core property used is: For any two positive integers $a$ and $b$, where $a > b$, HCF$(a, b) =$ HCF$(b, r)$, where $r$ is the remainder when $a$ is divided by $b$ ($a = bq + r$, where $0 \le r < b$).

Steps to find the HCF of two positive integers $a$ and $b$ (assume $a \ge b$):

1. Divide $a$ by $b$ and find the remainder, $r$.
2. If the remainder $r$ is $0$, the current divisor $b$ is the HCF of the original two numbers. The process terminates.
3. If the remainder $r$ is not $0$, replace the dividend ($a$) with the current divisor ($b$) and the divisor ($b$) with the current remainder ($r$). Effectively, you start the division process again with the previous divisor as the new dividend and the remainder as the new divisor.
4. Continue this iterative process until a remainder of $0$ is obtained. The divisor at the step where the remainder is $0$ is the HCF of the original two numbers.

Answer:

Finding HCF of More Than Two Numbers using Euclidean Algorithm

To find the HCF of three or more numbers (say, $a, b, c$), you can find the HCF of any two of the numbers first. Let HCF$(a, b) = d_1$. Then, the HCF of the original three numbers is the HCF of $d_1$ and the third number $c$. HCF$(a, b, c) =$ HCF(HCF$(a, b), c) =$ HCF$(d_1, c)$. This process can be extended for any number of integers.

Example: Find HCF$(12, 18, 30)$.

First, find HCF$(12, 18)$. Using prime factorization: $12 = 2^2 \times 3$, $18 = 2 \times 3^2$. HCF$(12, 18) = 2^1 \times 3^1 = 6$.

Now, find HCF(6, 30). Using the division method: Divide 30 by 6. $30 \div 6 = 5$ with remainder 0. The divisor is 6. So, HCF$(6, 30) = 6$.

Thus, HCF$(12, 18, 30) = \mathbf{6}$.

---

Properties of HCF

For any positive integers $a$ and $b$:

• HCF$(a, b)$ is always a factor of both $a$ and $b$.
• HCF$(a, b) \le \min(a, b)$ (The HCF is less than or equal to the smaller of the two numbers).
• If $b$ divides $a$ exactly (i.e., $b|a$), then HCF$(a, b) = b$. Example: HCF$(20, 5) = 5$.
• HCF$(a, b) = \text{HCF}(b, a)$. The order of the numbers does not matter.
• HCF$(a, 1) = 1$ for any positive integer $a$. The only common positive factor of any integer and 1 is 1.
• HCF$(a, 0) = a$ for any positive integer $a$. (Based on the definition that the largest divisor of $a$ that also divides 0 is $a$, since any non-zero number divides 0). Note that HCF$(0, 0)$ is usually undefined in elementary contexts, or defined as 0.
• HCF$(a, a) = a$ for any positive integer $a$.
• Two positive integers $a$ and $b$ are called co-prime or relatively prime if their only common positive factor is $1$, which means HCF$(a, b) = 1$. Example: HCF$(8, 15) = 1$, so 8 and 15 are co-prime.

Understanding HCF and the methods to find it is important for problems involving common factors, such as simplifying fractions and solving word problems involving division into equal parts.

Least Common Multiple (LCM): Definition and Methods

---

Defining the Least Common Multiple (LCM)

The Least Common Multiple (LCM) of two or more non-zero integers is the smallest positive integer that is a multiple of each of the given integers. It is the smallest positive number that is "common" to the list of multiples of each number.

To understand LCM, let's consider the multiples of numbers:

• Multiples: As defined previously, a multiple of a non-zero integer $n$ is any number that can be obtained by multiplying $n$ by an integer. For example, the multiples of 6 are $\ldots, -18, -12, -6, 0, 6, 12, 18, 24, 30, \ldots$. The positive multiples are $6, 12, 18, 24, 30, \ldots$.
• Common Multiples: For a set of two or more non-zero integers, the common multiples are the numbers that are multiples of all the numbers in the set. For example, the positive multiples of 6 are $\{6, 12, 18, \underline{24}, 30, 36, 42, \underline{48}, \ldots\}$, and the positive multiples of 8 are $\{8, 16, \underline{24}, 32, 40, \underline{48}, 56, \ldots\}$. The positive common multiples of 6 and 8 are $\{24, 48, 72, 96, \ldots\}$.
• Least Common Multiple: Among the positive common multiples, the LCM is the smallest one. In the example of 6 and 8, the positive common multiples are $\{24, 48, 72, \ldots\}$. The smallest number in this set is 24. Therefore, the Least Common Multiple of 6 and 8 is 24. LCM(6, 8) = 24.

The LCM is only defined for non-zero integers because the multiples of 0 are only 0, and finding a "least common positive multiple" with 0 is not meaningful in the standard definition.

---

Methods for Calculating LCM

Several methods exist for calculating the LCM of two or more numbers. The choice depends on the context and the size of the numbers.

Method 1: Listing Common Multiples

This is the most basic method. You list the positive multiples of each number until you find the first number that appears in all the lists.

Steps:

1. List the first few positive multiples of the first number.
2. List the first few positive multiples of the second number.
3. Continue listing multiples for all numbers until you find the smallest number that is present in all the lists.
4. This first common positive multiple is the LCM.

Answer:

This method is practical for small numbers but becomes inefficient if the LCM is large.

Method 2: Prime Factorisation Method

This method is based on the prime factorization of each number and is generally more efficient for larger numbers than listing multiples.

Steps:

1. Find the prime factorization of each of the given numbers. Express the factorizations in exponential form (e.g., $p_1^{e_1} \times p_2^{e_2} \times \ldots$).
2. List all the distinct prime factors that appear in *any* of the factorizations of the numbers.
3. For each distinct prime factor, select the highest exponent (power) to which it is raised across all the factorizations.
4. Multiply these selected highest powers of all distinct prime factors together. The product is the LCM.

Answer:

Method 3: Division Method (Common Division Method)

This is a very practical and efficient method for finding the LCM of two or more numbers simultaneously. It involves repeatedly dividing the numbers by their common prime factors, or by any prime factor that divides at least one of the numbers.

Steps to find the LCM of two or more numbers:

1. Write the given numbers in a row, separated by commas.
2. Find the smallest prime number that divides at least one of the given numbers. Write this prime number to the left of the row and draw a vertical line.
3. Divide each number in the row by this prime number and write the quotient below it in the next row. If a number is not divisible by the prime, write it as is in the next row.
4. Repeat the process with the numbers in the new row. Find the smallest prime that divides at least one of them, divide, and write the results in the next row.
5. Continue this process until all the numbers in the last row are 1.
6. The LCM is the product of all the prime divisors used in the process (the numbers to the left of the vertical lines) and the numbers in the last row (which will all be 1).

Answer:

---

Properties of LCM

For any positive integers $a$ and $b$:

• LCM$(a, b)$ is always a multiple of both $a$ and $b$. It is the smallest positive such multiple.
• LCM$(a, b) \ge \max(a, b)$ (The LCM is greater than or equal to the larger of the two numbers).
• If $b$ divides $a$ exactly (i.e., $b|a$), then LCM$(a, b) = a$. Example: LCM$(20, 5) = 20$. (Since 20 is a multiple of 5).
• LCM$(a, b) = \text{LCM}(b, a)$. The order of the numbers does not matter.
• LCM$(a, 1) = a$ for any positive integer $a$. The smallest positive common multiple of $a$ and 1 is $a$.
• LCM$(a, 0)$ is generally undefined in the standard definition of LCM for non-zero integers. If 0 is included, 0 is the only common multiple of any number and 0, so LCM might be defined as 0.
• LCM$(a, a) = a$ for any positive integer $a$. The smallest common multiple of a number and itself is the number itself.
• If $a$ and $b$ are co-prime (their Greatest Common Divisor is 1, HCF$(a, b) = 1$), then their LCM is simply the product of the two numbers: LCM$(a, b) = a \times b$. Example: HCF$(5, 7) = 1$, LCM$(5, 7) = 5 \times 7 = 35$. HCF$(8, 9) = 1$, LCM$(8, 9) = 8 \times 9 = 72$.

Finding the LCM is important in various mathematical problems, especially when adding or subtracting fractions with unlike denominators, where the LCM is used as the least common denominator.

Relation between HCF and LCM of Two Natural Numbers

For any two positive integers (natural numbers), there exists a fundamental and extremely useful relationship between their Highest Common Factor (HCF) and their Least Common Multiple (LCM). This relationship simplifies calculations and allows us to find one value if others are known.

---

The Fundamental Relationship

For any two positive integers, $a$ and $b$, the product of their Highest Common Factor (HCF) and their Least Common Multiple (LCM) is equal to the product of the numbers themselves.

This can be stated as:

This relationship holds strictly for two positive integers. While related properties exist for more than two numbers, this specific formula is for a pair of numbers.

---

Derivation/Verification of the Relationship using Prime Factorization

The relationship between HCF, LCM, and the product of two numbers can be clearly understood and verified using their prime factorizations. The Fundamental Theorem of Arithmetic guarantees that every positive integer greater than 1 has a unique prime factorization.

Let $a$ and $b$ be two positive integers. Let their prime factorizations be:

$a = p_1^{e_1} p_2^{e_2} p_3^{e_3} \ldots p_k^{e_k}$

$b = p_1^{f_1} p_2^{f_2} p_3^{f_3} \ldots p_k^{f_k}$

where $p_1, p_2, \ldots, p_k$ are all the distinct prime factors that appear in the factorization of either $a$ or $b$. The exponents $e_i$ and $f_i$ are non-negative integers. If a prime $p_i$ is not a factor of a number (e.g., $p_i \nmid a$), its corresponding exponent $e_i$ is considered to be $0$.

Based on the prime factorization methods for HCF and LCM:

• The HCF of $a$ and $b$ is found by taking the product of the common prime factors, each raised to the lowest power it appears in either factorization. $$ \text{HCF}(a, b) = p_1^{\min(e_1, f_1)} p_2^{\min(e_2, f_2)} \ldots p_k^{\min(e_k, f_k)} $$
• The LCM of $a$ and $b$ is found by taking the product of all distinct prime factors that appear in either factorization, each raised to the highest power it appears. $$ \text{LCM}(a, b) = p_1^{\max(e_1, f_1)} p_2^{\max(e_2, f_2)} \ldots p_k^{\max(e_k, f_k)} $$

Now, let's consider the product of HCF$(a, b)$ and LCM$(a, b)$:

$$ \text{HCF}(a, b) \times \text{LCM}(a, b) = \left(p_1^{\min(e_1, f_1)} p_2^{\min(e_2, f_2)} \ldots p_k^{\min(e_k, f_k)}\right) \times \left(p_1^{\max(e_1, f_1)} p_2^{\max(e_2, f_2)} \ldots p_k^{\max(e_k, f_k)}\right) $$

Using the property of exponents for multiplication with the same base ($p_i^x \times p_i^y = p_i^{x+y}$), we can group the terms for each prime factor $p_i$:

$$ \text{HCF}(a, b) \times \text{LCM}(a, b) = p_1^{\min(e_1, f_1) + \max(e_1, f_1)} \times p_2^{\min(e_2, f_2) + \max(e_2, f_2)} \times \ldots \times p_k^{\min(e_k, f_k) + \max(e_k, f_k)} $$

For any two real numbers $x$ and $y$, the sum of their minimum and maximum is always equal to their sum: $\min(x, y) + \max(x, y) = x + y$. This applies to the exponents $e_i$ and $f_i$.

So, for each prime factor $p_i$, the exponent in the product (HCF $\times$ LCM) is $e_i + f_i$.

$$ \text{HCF}(a, b) \times \text{LCM}(a, b) = p_1^{e_1 + f_1} p_2^{e_2 + f_2} \ldots p_k^{e_k + f_k} $$

Now, let's consider the product of the original numbers, $a \times b$:

$$ a \times b = (p_1^{e_1} p_2^{e_2} \ldots p_k^{e_k}) \times (p_1^{f_1} p_2^{f_2} \ldots p_k^{f_k}) $$

Using the commutative and associative properties of multiplication, and the rule of exponents ($p_i^{e_i} \times p_i^{f_i} = p_i^{e_i + f_i}$):

$$ a \times b = (p_1^{e_1} p_1^{f_1}) \times (p_2^{e_2} p_2^{f_2}) \times \ldots \times (p_k^{e_k} p_k^{f_k}) $$ $$ a \times b = p_1^{e_1 + f_1} \times p_2^{e_2 + f_2} \times \ldots \times p_k^{e_k + f_k} $$

Comparing the final expressions for HCF$(a, b) \times \text{LCM}(a, b)$ and $a \times b$, we see that they are identical.

This derivation using prime factorization proves the relationship HCF$(a, b) \times \text{LCM}(a, b) = a \times b$ for any two positive integers $a$ and $b$.

---

Utilizing the Relationship

The formula HCF$(a, b) \times \text{LCM}(a, b) = a \times b$ is extremely useful because if you know any three of the four values (the two numbers, their HCF, and their LCM), you can easily find the fourth value by rearranging the formula:

• To find the LCM when HCF and the numbers are known: $\quad \text{LCM}(a, b) = \frac{a \times b}{\text{HCF}(a, b)}$
• To find the HCF when LCM and the numbers are known: $\quad \text{HCF}(a, b) = \frac{a \times b}{\text{LCM}(a, b)}$
• To find one of the numbers when the other number, HCF, and LCM are known: $\quad a = \frac{\text{HCF}(a, b) \times \text{LCM}(a, b)}{b} \quad$ or $\quad b = \frac{\text{HCF}(a, b) \times \text{LCM}(a, b)}{a}$

These derived formulas are very useful in problem-solving.

Answer:

---

Answer:

The relationship HCF$(a, b) \times \text{LCM}(a, b) = a \times b$ is a critical tool when working with HCF and LCM problems involving exactly two natural numbers. It should be used with caution when dealing with more than two numbers.

Applications of HCF and LCM

The concepts of Highest Common Factor (HCF) and Least Common Multiple (LCM) are not just theoretical tools; they have practical applications in solving various types of problems in mathematics and real-life situations. These applications often involve scenarios where we need to find common factors or common multiples of given quantities or time intervals.

---

Applications of HCF (Greatest Common Divisor - GCD)

HCF is typically applied in problems where you need to divide, cut, or group items into the largest possible equal-sized portions or to find the largest possible unit of measurement that fits evenly into given quantities. Look for keywords like "largest", "greatest", "maximum size", "equal groups", "most number of...", etc., in the context of division or grouping.

Common applications of HCF include:

1. Dividing Articles or Quantities into Largest Equal Parts: This is a classic HCF problem. When you have different quantities (lengths, weights, volumes, counts of items) and need to divide them into pieces of the largest possible equal size without any leftovers, you find the HCF of the quantities.

   Example: A tailor has two pieces of fabric of lengths $24 \text{ metres}$ and $32 \text{ metres}$. He wants to cut both pieces into smaller pieces of equal length, and the length of each smaller piece must be the maximum possible. What is the length of each smaller piece?

   The length of the smaller pieces must be a common factor of both 24 m and 32 m, so that both pieces can be cut exactly. To make the pieces the maximum possible equal length, we need the Highest Common Factor of 24 and 32.

   Example 1. Find the maximum length of each smaller piece of fabric, given pieces of $24 \text{ m}$ and $32 \text{ m}$.

   Answer:

   We need to find HCF$(24, 32)$. We can use the prime factorization method or the division method.

   Using prime factorization:

   Prime factorization of $24 = 2^3 \times 3^1$

   Prime factorization of $32 = 2^5$

   The only common prime factor is 2. The lowest power of 2 that appears in both is $2^3$.

   HCF$(24, 32) = 2^3 = 8$.

   The maximum length of each smaller piece is $\mathbf{8 \text{ metres}}$.

   With 8-metre pieces: from the 24 m fabric, $24 \div 8 = 3$ pieces. From the 32 m fabric, $32 \div 8 = 4$ pieces.

2. Arranging or Tiling in Largest Squares: Finding the largest square unit that can perfectly tile a rectangular area (like a floor, wall, or courtyard) involves finding the HCF of the dimensions of the rectangle. The side length of the square tile must divide both the length and the width of the rectangle, and we want the largest such side length, which is the HCF.

   Example: A rectangular courtyard is $18 \text{ m}$ long and $15 \text{ m}$ wide. It is to be paved with square tiles of the same size without cutting any tile. Find the largest size of the tile required.

   The side length of the square tile must be a common factor of the length (18 m) and the width (15 m). The largest such side length is the HCF of 18 and 15.

   Example 2. Find the side length of the largest square tile to pave an $18 \text{ m} \times 15 \text{ m}$ courtyard.

   Answer:

   We need to find HCF$(18, 15)$. Using the listing common factors method:

   Factors of $18$: $1, 2, 3, 6, 9, 18$.

   Factors of $15$: $1, 3, 5, 15$.

   The common factors are the numbers present in both lists: $1, 3$.

   The largest among these common factors is 3.

   So, HCF$(18, 15) = 3$.

   The largest size of the square tile required is $\mathbf{3 \text{ m} \times 3 \text{ m}}$.

   Number of tiles along the length = $18 \div 3 = 6$. Number of tiles along the width = $15 \div 3 = 5$. Total tiles = $6 \times 5 = 30$.

3. Simplifying Fractions: The most efficient way to reduce a fraction to its simplest form is to divide both the numerator and the denominator by their HCF. Example: $\frac{12}{18}$. HCF$(12, 18) = 6$. Divide numerator and denominator by 6: $\frac{12 \div 6}{18 \div 6} = \frac{2}{3}$.

---

Applications of LCM (Least Common Multiple)

LCM is typically applied in problems that involve finding the smallest common quantity or time interval that is a multiple of two or more given quantities or intervals. These problems often relate to events that repeat or coincide periodically. Look for keywords like "smallest number", "least number", "minimum time", "meet again", "cycle repeats", etc., in the context of repeating events or finding a common total that can be divided by the given numbers.

Common applications of LCM include:

1. Finding When Events Coincide: If different events occur at regular intervals, the LCM helps determine when they will next happen simultaneously.

   Example: Three friends, Rohan, Priya, and Amit, start running around a circular track at the same point and at the same time. Rohan completes one round in $15$ minutes, Priya in $20$ minutes, and Amit in $25$ minutes. After how many minutes will they all meet again at the starting point for the first time?

   Rohan will be at the starting point after 15, 30, 45, ... minutes (multiples of 15). Priya will be there after 20, 40, 60, ... minutes (multiples of 20). Amit will be there after 25, 50, 75, ... minutes (multiples of 25).

   They will all meet at the starting point when the time elapsed is a common multiple of 15, 20, and 25. We need the smallest such common multiple, which is the LCM of 15, 20, and 25.

   Example 3. Find the LCM of $15, 20,$ and $25$.

   Answer:

   We can use the prime factorization method or the division method. Using the division method:

   Divide by the smallest prime (2) that divides at least one number (20):

   $$ \begin{array}{c|cc} 2 & 15 \;, & 20 \;, & 25 \\ \hline 3 & 15 \; , & 10 \; , & 25 \\ \hline 5 & 5 \; , & 10 \; , & 25 \\ \hline 5 & 1 \; , & 2 \; , & 5 \\ \hline 2 & 1 \; , & 2 \; , & 1 \\ \hline & 1 \; , & 1 \; , & 1 \end{array} $$

   Corrected steps for division method:

   $$ \begin{array}{c|cc} 2 & 15 \;, & 20 \;, & 25 \\ \hline 2 & 15 \; , & 10 \; , & 25 \\ \hline 3 & 15 \; , & 5 \; , & 25 \\ \hline 5 & 5 \; , & 5 \; , & 25 \\ \hline 5 & 1 \; , & 1 \; , & 5 \\ \hline & 1 \; , & 1 \; , & 1 \end{array} $$

   The prime divisors used on the left are $2, 2, 3, 5, 5$.

   LCM = $2 \times 2 \times 3 \times 5 \times 5 = 2^2 \times 3^1 \times 5^2 = 4 \times 3 \times 25 = 12 \times 25 = 300$.

   They will meet again at the starting point for the first time after $\mathbf{300}$ minutes (which is $5$ hours).

2. Finding the Smallest Common Quantity: Determining the smallest number of items required so that they can be perfectly grouped into different specified sizes without any leftovers.

   Example: What is the smallest number which when divided by $8, 12,$ and $15$ leaves a remainder of $0$ in each case?

   The required number must be a multiple of 8, 12, and 15. We need the smallest such positive number, which is the LCM of 8, 12, and 15.

   Example 4. Find the LCM of $8, 12,$ and $15$.

   Answer:

   Using the division method:

   $$ \begin{array}{c|cc} 2 & 8 \;, & 12 \;, & 15 \\ \hline 2 & 4 \; , & 6 \; , & 15 \\ \hline 2 & 2 \; , & 3 \; , & 15 \\ \hline 3 & 1 \; , & 3 \; , & 15 \\ \hline 5 & 1 \; , & 1 \; , & 5 \\ \hline & 1 \; , & 1 \; , & 1 \end{array} $$

   The prime divisors used on the left are $2, 2, 2, 3, 5$.

   LCM = $2 \times 2 \times 2 \times 3 \times 5 = 2^3 \times 3^1 \times 5^1 = 8 \times 3 \times 5 = 120$.

   The smallest number which is divisible by 8, 12, and 15 is $\mathbf{120}$. (Check: $120 \div 8 = 15$, $120 \div 12 = 10$, $120 \div 15 = 8$).

3. Solving problems with remainders: If a problem asks for the smallest number which when divided by $a, b,$ and $c$ leaves a specific remainder $r$ in each case (where $r$ is less than $a, b,$ and $c$), the number is LCM$(a, b, c) + r$. This is because (LCM$(a, b, c) + r) - r =$ LCM$(a, b, c)$, which is divisible by $a, b,$ and $c$.

   Example: What is the smallest number which when divided by 8, 12, and 15 leaves a remainder of 5 in each case?

   From the previous example, LCM$(8, 12, 15) = 120$. The required number is $120 + 5 = 125$. (Check: $125 \div 8 = 15$ R 5, $125 \div 12 = 10$ R 5, $125 \div 15 = 8$ R 5).

4. Adding and Subtracting Fractions: The LCM of the denominators of unlike fractions is used as the Least Common Denominator (LCD) to convert them into equivalent like fractions before adding or subtracting.

Both HCF and LCM are fundamental concepts that are applied in solving a wide variety of problems involving integers, making them essential tools in arithmetic and number theory.