Prime Factorization: HCF and LCM

Welcome back. In our previous lesson, we explored the Fundamental Theorem of Arithmetic, establishing that prime numbers are the unique, fundamental building blocks of all composite numbers. You learned how to perform prime factorization, a skill that serves as the foundation for today's topic.

Today, we will directly apply that knowledge to develop a powerful and systematic method for finding the Highest Common Factor (HCF) and Lowest Common Multiple (LCM) of integers. While you might recall finding HCF and LCM by listing factors or multiples, the prime factorization method is far more efficient and scalable, especially for larger numbers. Understanding this method is not just about calculation; it reveals the deep connection between the factors of numbers and their prime "DNA."

A Quick Refresher: HCF and LCM

Before we dive into the new method, let's briefly revisit the core definitions of HCF and LCM. This will ensure our foundational concepts are solid.

Highest Common Factor (HCF): The HCF of two or more numbers is the largest positive integer that divides each of the numbers without leaving a remainder. For example, the factors of 12 are {1, 2, 3, 4, 6, 12} and the factors of 18 are {1, 2, 3, 6, 9, 18}. The common factors are {1, 2, 3, 6}, and the highest among them is 6. So, HCF(12, 18) = 6.
Lowest Common Multiple (LCM): The LCM of two or more numbers is the smallest positive integer that is a multiple of all the numbers. For example, multiples of 12 are {12, 24, 36, 48, ...} and multiples of 18 are {18, 36, 54, ...}. The first multiple they have in common is 36. So, LCM(12, 18) = 36.

Listing factors and multiples works for small numbers, but it quickly becomes cumbersome. Prime factorization provides a more elegant and algorithmic approach.

Finding HCF and LCM using Prime Factorization

The beauty of the Fundamental Theorem of Arithmetic is that it allows us to analyze the properties of a number by looking at its prime factors. Let's see how this applies to HCF and LCM.

The Method

Prime Factorize: Express each number as a product of its prime factors, preferably in index form (e.g., $2^{3} \times 3^{1}$ ).
Find the HCF: The HCF is the product of the lowest powers of all common prime factors. If a prime factor is not common to all numbers, its power is considered to be 0 for this calculation.
Find the LCM: The LCM is the product of the highest powers of all prime factors that appear in any of the numbers.

Let's formalize this, as the underlying logic is quite systematic. Given two numbers, $a$ and $b$ , with their prime factorizations:

a = p_{1}^{x_{1}} \times p_{2}^{x_{2}} \times \dots \times p_{k}^{x_{k}}

b = p_{1}^{y_{1}} \times p_{2}^{y_{2}} \times \dots \times p_{k}^{y_{k}}

(Note: we list all primes present in either $a$ or $b$ , and if a prime is not present in one number, its exponent is 0. For example, if $a = 12 = 2^{2} \times 3^{1}$ and $b = 20 = 2^{2} \times 5^{1}$ , we can write them as $a = 2^{2} \times 3^{1} \times 5^{0}$ and $b = 2^{2} \times 3^{0} \times 5^{1}$ .)

Then:

HCF (a, b) = p_{1}^{m i n (x_{1}, y_{1})} \times p_{2}^{m i n (x_{2}, y_{2})} \times \dots \times p_{k}^{m i n (x_{k}, y_{k})}

LCM (a, b) = p_{1}^{m a x (x_{1}, y_{1})} \times p_{2}^{m a x (x_{2}, y_{2})} \times \dots \times p_{k}^{m a x (x_{k}, y_{k})}

Why does this work for HCF? The HCF must divide both numbers. This is only possible if its prime factors are a subset of the prime factors of both numbers. By taking the minimum power of each common prime, we are finding the largest possible set of prime factors that is contained within both original numbers.
Why does this work for LCM? The LCM must be divisible by both numbers. This requires its prime factorization to contain all the prime factors of the first number and all the prime factors of the second number. By taking the maximum power of every prime involved, we construct the smallest possible number that satisfies this condition for both.

A Visual Approach: Venn Diagrams

A Venn diagram offers a powerful visual representation of this process. It helps to intuitively organize the prime factors.

This image illustrates the process for numbers 40 and 56. The prime factors of each number are found using factor trees. These factors are then placed in a Venn diagram. The intersection contains the common factors, while the outer sections contain the unique factors.

Let's analyze the image:

$40 = 2 \times 2 \times 2 \times 5$
$56 = 2 \times 2 \times 2 \times 7$
The common factors are three 2s. These go into the intersection of the Venn diagram.
The remaining factor for 40 is 5, and for 56 is 7. These go into the non-overlapping parts of their respective circles.

From this diagram:

HCF: The product of the numbers in the intersection.
HCF(40, 56) = $2 \times 2 \times 2 = 8$ . This aligns with our rule of taking the lowest powers of common factors.
LCM: The product of all numbers in the diagram (the union).
LCM(40, 56) = $(5) \times (2 \times 2 \times 2) \times (7) = 280$ . This aligns with our rule of taking the highest powers of all factors.

To solidify this method, let's review a clear, step-by-step guide.

Prime Factors LCM HCF Worksheets, Questions and Revision

This resource from MME Revise provides a detailed walkthrough of using Venn diagrams to find the HCF and LCM for the numbers 60 and 27. It clearly shows how to populate the diagram from the prime factorizations.

Please read the section titled HCF and LCM – Venn Diagrams. Focus on the logic of placing common factors in the intersection and unique factors in the outer parts.

Walkthrough and an Important Property

Now, let's watch a short video that demonstrates this process using the "powers" method, which is a more direct computational approach without drawing diagrams.

4 Finding HCF and LCM using Fundamental theorem of Arithmetic

This video from Arinjay Jain Academy clearly explains the rules for finding HCF and LCM using the minimum and maximum powers of prime factors.

Watch the entire video from the beginning. The presenter calculates the HCF and LCM of 84 and 144. Pay close attention to the counter-intuitive but correct logic: for the Highest Common Factor, you take the lowest powers, and for the Least Common Multiple, you take the highest powers.

An Important Relationship for Two Numbers

There is a very useful relationship that connects the HCF and LCM of two numbers with the numbers themselves:

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

HCF (a, b) \times LCM (a, b) = a \times b

This is not a coincidence, and its proof stems directly from the method we just learned. For any prime factor $p$ , its exponent in the product $a \times b$ is $x + y$ . Its exponent in the product $HCF \times LCM$ is $min (x, y) + max (x, y)$ . A key property of numbers is that for any two values $x$ and $y$ , $min (x, y) + max (x, y) = x + y$ . Since this holds true for the exponents of every prime factor, the overall products must be equal.

This formula is excellent for verifying your calculations. If you've found the HCF and LCM, multiply them together and check if the result equals the product of the original two numbers.

Extending to Three Numbers

The prime factorization method extends seamlessly to three or more numbers.

HCF: The product of the lowest powers of prime factors that are common to all the numbers.
LCM: The product of the highest powers of all prime factors present in any of the numbers.

The image below shows an example for 60, 168, and 330.

Here, the prime factorizations are listed. For HCF, the common factors (2 and 3) are multiplied. For LCM, all factors are included at their highest powers to get the final result.

Let's analyze the image:

$60 = 2^{2} \times 3^{1} \times 5^{1}$
$168 = 2^{3} \times 3^{1} \times 7^{1}$
$330 = 2^{1} \times 3^{1} \times 5^{1} \times 1 1^{1}$

To find the HCF:
The common prime factors are 2 and 3.

Lowest power of 2: $2^{1}$ (from 330)
Lowest power of 3: $3^{1}$ (from all three)
HCF = $2^{1} \times 3^{1} = 6$

To find the LCM:
The prime factors involved are 2, 3, 5, 7, and 11.

Highest power of 2: $2^{3}$ (from 168)
Highest power of 3: $3^{1}$ (from all three)
Highest power of 5: $5^{1}$ (from 60 and 330)
Highest power of 7: $7^{1}$ (from 168)
Highest power of 11: $1 1^{1}$ (from 330)
LCM = $2^{3} \times 3^{1} \times 5^{1} \times 7^{1} \times 1 1^{1} = 8 \times 3 \times 5 \times 7 \times 11 = 9240$

Important Note: The property $HCF \times LCM = a \times b$ does not generally hold for three or more numbers.

Check Your Understanding

Find the HCF and LCM of 90 and 144 using the prime factorization method. You can use the power rules or a Venn diagram. Verify your answer for these two numbers using the property $HCF \times LCM = a \times b$ .

Click to see the solution

Prime Factorization:
- $90 = 2 \times 45 = 2 \times 9 \times 5 = 2^{1} \times 3^{2} \times 5^{1}$
- $144 = 12 \times 12 = (2^{2} \times 3) \times (2^{2} \times 3) = 2^{4} \times 3^{2}$
Find HCF (lowest powers of common factors):
- Common factors are 2 and 3.
- Lowest power of 2: $min (1, 4) = 1$ , so we take $2^{1}$ .
- Lowest power of 3: $min (2, 2) = 2$ , so we take $3^{2}$ .
- HCF = $2^{1} \times 3^{2} = 2 \times 9 = 18$ .
Find LCM (highest powers of all factors):
- All factors are 2, 3, and 5.
- Highest power of 2: $max (1, 4) = 4$ , so we take $2^{4}$ .
- Highest power of 3: $max (2, 2) = 2$ , so we take $3^{2}$ .
- Highest power of 5: $max (1, 0) = 1$ , so we take $5^{1}$ .
- LCM = $2^{4} \times 3^{2} \times 5^{1} = 16 \times 9 \times 5 = 144 \times 5 = 720$ .
Verification:
- $HCF \times LCM = 18 \times 720 = 12960$
- $a \times b = 90 \times 144 = 12960$
- The results match.

Conclusion

In this lesson, we built upon the Fundamental Theorem of Arithmetic to create a robust, algorithm-based method for finding the HCF and LCM. This technique not only streamlines calculations but also reinforces the concept of prime numbers as the elementary components of integers.

Key Takeaways:

To find the HCF using prime factorization, you multiply the lowest powers of all common prime factors.
To find the LCM, you multiply the highest powers of all prime factors present in any of the numbers.
Venn diagrams serve as an excellent visual aid for this method, where the intersection represents the factors for the HCF, and the union represents the factors for the LCM.
For any two positive integers $a$ and $b$ , the product of the numbers is equal to the product of their HCF and LCM: $a \times b = HCF (a, b) \times LCM (a, b)$ .

We have now concluded our exploration of the core computational aspects of real numbers in this module. In our next lesson, we will shift gears from calculation to formal proof. We will tackle the classic and important task of proving the irrationality of numbers like $2$ , $3$ , and $5$ using the method of contradiction.

Recommended resources