HCF or GCD and LCM using prime factorization

Determining HCF (or GCD) and LCM Through Prime Factorization

In arithmetic, understanding how numbers relate to one another in terms of factors and multiples is important. Two such key concepts are: Highest Common Factor (HCF or GCD) and Least Common Multiple (LCM).

What Is HCF or GCD?

The HCF (Highest Common Factor), also known as the GCD (Greatest Common Divisor), of two or more numbers is the largest number that divides each of them exactly without leaving a remainder.

What Is LCM?

The LCM (Least Common Multiple) of two or more numbers is the smallest number that is a multiple of all the given numbers.

Using Prime Factorization to Determine HCF and LCM

A reliable method for determining both HCF and LCM is through the use of prime factorization. Here's how:

Steps:

1. Find the prime factorization of each number.
2. To find HCF: Take the product of all common prime factors with the lowest powers.
3. To calculate the LCM, multiply all the prime factors involved, using the greatest exponent for each.

Example:

Determine the HCF and LCM of 60 and 72 by applying prime factorization.

Step 1: Prime Factorization

• 60 = 2² × 3 × 5
• 72 = 2³ × 3²

Step 2: HCF

Common prime factors are 2 and 3
Lowest power of 2 = 2²
Lowest power of 3 = 3¹
So, HCF = 2² × 3 = 4 × 3 = 12

Step 3: LCM

All prime factors involved are 2, 3, 5
Highest power of 2 = 2³
Highest power of 3 = 3²
Highest power of 5 = 5¹
So, LCM = 2³ × 3² × 5 = 8 × 9 × 5 = 360

Quick Tip:

Once you know the HCF and LCM of two numbers, their product will always equal the product of the original two numbers:

HCF × LCM = Number 1 × Number 2
For example: 12 × 360 = 60 × 72 = 4320

Using prime factorization is an effective method to determine both the HCF and the LCM of numbers. It breaks numbers down into their building blocks and allows for a clear, structured method to find the greatest common divisor and least common multiple.