TNPSC Group 1 - Highest common factor HCF and lowest common multiple LCM. E-Book Study Material

```html

Highest Common Factor (HCF) and Lowest Common Multiple (LCM)

In mathematics, the concepts of Highest Common Factor (HCF) and Lowest Common Multiple (LCM) are fundamental, especially in number theory. They are crucial for simplifying fractions, solving problems involving ratios, and understanding divisibility rules. HCF, also known as the Greatest Common Divisor (GCD), is the largest positive integer that divides two or more integers without leaving a remainder. LCM, on the other hand, is the smallest positive integer that is a multiple of two or more integers. Understanding these concepts is vital for tackling aptitude and mental ability questions in competitive exams.

Understanding Factors and Multiples

Before diving into HCF and LCM, let's clarify what factors and multiples are.

Factors

A factor of a number is any integer that divides the number evenly, meaning there is no remainder. For example, the factors of 12 are 1, 2, 3, 4, 6, and 12 because each of these numbers divides 12 without leaving a remainder.

Multiples

A multiple of a number is the result of multiplying that number by any integer. For example, the multiples of 5 are 5, 10, 15, 20, 25, and so on. These are obtained by multiplying 5 by 1, 2, 3, 4, 5, etc.

Highest Common Factor (HCF)

The Highest Common Factor (HCF) of two or more numbers is the largest positive integer that divides each of the numbers without leaving a remainder.

Methods to Find HCF

There are several methods to find the HCF of a set of numbers:

Method 1: Listing Factors

This method involves listing all the factors of each number and then identifying the largest factor that appears in all the lists.

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

The common factors are 1, 2, 3, and 6. The highest among these common factors is 6.

Therefore, HCF(12, 18) = 6.

Method 2: Prime Factorization

This is a more systematic method, especially for larger numbers. It involves breaking down each number into its prime factors and then multiplying the common prime factors raised to the lowest power they appear in any of the factorizations.

Example: Find the HCF of 24 and 36.

Prime factorization of 24:

$24 = 2 \times 12 = 2 \times 2 \times 6 = 2 \times 2 \times 2 \times 3 = 2^3 \times 3^1$

Prime factorization of 36:

$36 = 2 \times 18 = 2 \times 2 \times 9 = 2 \times 2 \times 3 \times 3 = 2^2 \times 3^2$

To find the HCF, we take the common prime factors and the lowest power of each common prime factor:

Common prime factor is 2. The lowest power of 2 is $2^2$.
Common prime factor is 3. The lowest power of 3 is $3^1$.

HCF(24, 36) = $2^2 \times 3^1 = 4 \times 3 = 12$.

Method 3: Division Method (Euclidean Algorithm)

This method is efficient for finding the HCF of two numbers. It is based on the principle that the HCF 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 number is the HCF. A more common implementation uses division: the HCF of two numbers is the same as the HCF of the smaller number and the remainder when the larger number is divided by the smaller number.

Example: Find the HCF of 135 and 225.

Divide 225 by 135: $225 = 1 \times 135 + 90$
Now, find the HCF of 135 and the remainder 90. Divide 135 by 90: $135 = 1 \times 90 + 45$
Now, find the HCF of 90 and the remainder 45. Divide 90 by 45: $90 = 2 \times 45 + 0$

The last non-zero remainder is the HCF. In this case, it is 45.

Therefore, HCF(135, 225) = 45.

HCF Shortcut (Euclidean Algorithm): For two numbers 'a' and 'b' (where a > b), HCF(a, b) = HCF(b, a mod b). Repeat until the remainder is 0. The last non-zero remainder is the HCF.

Lowest Common Multiple (LCM)

The Lowest Common Multiple (LCM) of two or more numbers is the smallest positive integer that is a multiple of all the numbers.

Methods to Find LCM

Similar to HCF, there are various methods to find the LCM:

Method 1: Listing Multiples

This involves listing the multiples of each number and finding the smallest multiple that appears in all the lists.

Example: Find the LCM of 4 and 6.

Multiples of 4: 4, 8, 12, 16, 20, 24, ...
Multiples of 6: 6, 12, 18, 24, 30, ...

The common multiples are 12, 24, etc. The smallest common multiple is 12.

Therefore, LCM(4, 6) = 12.

This method can be tedious for larger numbers.

Method 2: Prime Factorization

Break down each number into its prime factors. The LCM is obtained by multiplying the highest power of all prime factors that appear in any of the factorizations.

Example: Find the LCM of 24 and 36.

From the previous example, we have the prime factorizations:

$24 = 2^3 \times 3^1$
$36 = 2^2 \times 3^2$

To find the LCM, we take the highest power of each prime factor present in either factorization:

The prime factors involved are 2 and 3.
The highest power of 2 is $2^3$.
The highest power of 3 is $3^2$.

LCM(24, 36) = $2^3 \times 3^2 = 8 \times 9 = 72$.

Method 3: Division Method

This method is similar to the prime factorization method but is often presented in a tabular format. Write the numbers in a row and divide them by a common prime factor. Write the quotients in the next row. Repeat this process until all numbers in the row are prime to each other (i.e., their HCF is 1). The LCM is the product of the divisors and the numbers in the last row.

Example: Find the LCM of 12, 18, and 24.

2	12, 18, 24
2	6, 9, 12
3	3, 9, 6
3	1, 3, 2
-	1, 1, 2

The divisors are 2, 2, 3, 3. The remaining numbers in the last row are 1, 1, 2.

LCM(12, 18, 24) = $2 \times 2 \times 3 \times 3 \times 1 \times 1 \times 2 = 4 \times 9 \times 2 = 72$.

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) \times LCM(a, b) = a \times b$

This formula is extremely useful for solving problems where one of the values (HCF, LCM, or one of the numbers) is unknown.

Example: The HCF of two numbers is 12, and their LCM is 72. If one of the numbers is 24, find the other number.

Let the two numbers be 'a' and 'b'. We are given:

HCF(a, b) = 12
LCM(a, b) = 72
Let a = 24

Using the formula $HCF(a, b) \times LCM(a, b) = a \times b$:

$12 \times 72 = 24 \times b$

$b = \frac{12 \times 72}{24}$

$b = \frac{864}{24}$

$b = 36$

So, the other number is 36.

Formula Reminder: Product of two numbers = Product of their HCF and LCM. This is a shortcut to find one number if the other three values are known.

Applications of HCF and LCM

HCF and LCM have numerous applications in various mathematical problems, including:

Simplifying Fractions

To simplify a fraction to its lowest terms, we divide both the numerator and the denominator by their HCF.

Example: Simplify the fraction 48/72.

First, find the HCF of 48 and 72.

$48 = 2^4 \times 3^1$
$72 = 2^3 \times 3^2$
HCF(48, 72) = $2^3 \times 3^1 = 8 \times 3 = 24$

Now, divide the numerator and denominator by 24:

$\frac{48 \div 24}{72 \div 24} = \frac{2}{3}$

The simplified fraction is 2/3.

Problems involving Time and Cycles

LCM is often used in problems where events occur at regular intervals, and we need to find when they will occur simultaneously again.

Example: Three bells ring at intervals of 12 minutes, 15 minutes, and 18 minutes, respectively. If they all ring together at 8:00 AM, at what time will they next ring together?

We need to find the LCM of 12, 15, and 18.

$12 = 2^2 \times 3^1$
$15 = 3^1 \times 5^1$
$18 = 2^1 \times 3^2$

LCM(12, 15, 18) = $2^2 \times 3^2 \times 5^1 = 4 \times 9 \times 5 = 180$ minutes.

180 minutes is equal to 3 hours (180 / 60 = 3).

If they ring together at 8:00 AM, they will next ring together 3 hours later, which is 11:00 AM.

Problems involving Measurement and Division

HCF is useful when we need to find the largest possible unit of measurement that can be used to measure different quantities exactly, or to divide objects into equal parts of the largest possible size.

Example: A shopkeeper has 48 apples, 60 oranges, and 72 bananas. He wants to pack them into boxes such that each box contains the same number of fruits of only one type, and the number of fruits in each box is the largest possible. How many fruits will be in each box?

This requires finding the HCF of 48, 60, and 72.

$48 = 2^4 \times 3^1$
$60 = 2^2 \times 3^1 \times 5^1$
$72 = 2^3 \times 3^2$

HCF(48, 60, 72) = $2^2 \times 3^1 = 4 \times 3 = 12$.

So, each box will contain 12 fruits.

(To find the number of boxes: Apples: $48/12=4$ boxes, Oranges: $60/12=5$ boxes, Bananas: $72/12=6$ boxes. Total boxes = $4+5+6=15$ boxes.)

Practice Problems and Tips

To master HCF and LCM, consistent practice is key. Pay attention to the wording of the question, as it often indicates whether you need to find HCF or LCM.

If the question asks for the "largest number," "greatest number," or "maximum size," it usually implies HCF.
If the question asks for the "smallest number," "least number," "minimum time," or "next occurrence," it usually implies LCM.
Always simplify numbers before calculating HCF or LCM if possible (e.g., if all numbers are even, divide by 2 first, then multiply the final LCM by 2).
Remember the relationship: Product of numbers = HCF × LCM. This is a powerful shortcut.

Key takeaway for exams: Master the prime factorization method for both HCF and LCM as it is versatile. Remember the HCF × LCM = Product of numbers formula for quick problem-solving. For repeated events, think LCM; for division into equal largest parts, think HCF.

```