HCF by Prime Factorization Method

The greatest possible number that splits both integers exactly is called the highest common factor (HCF). The largest common divisor is another name for the highest common factor (HCF) (GCD). Let’s take a closer look at the HCF of two numbers and how to calculate it using prime factorization and division. Let’s look at how to calculate the HCF of two numbers using different ways.

HCF of Two Numbers by Prime Factorization

The highest common factor of two numbers, say p and q, is the number that is exactly divided by the largest possible number. The prime factorization of two prime numbers, say x and y, is shown when they are multiplied together. Prime factorization is represented by the product of two prime numbers. Let’s look at how the prime factorization method can be used to find the HCF of two numbers. We must take the following steps:

Determine each number’s prime factorization.

Make a list of those integers’ common prime factors.

Given numbers’ HCF is the product of common prime factors.

Let’s solve some HCF of two integers cases using prime factorization for a better understanding.

The HCFs of 56 and 84 will be found. We’ll use prime factorization to represent the numbers.

56 = 2 × 2 × 2 × 7 and 84 = 2 × 2 × 3 × 7  are the results. The product of common prime factors with the lowest exponential power, namely 7 and  2², will now be HCF of 56 and 84. As a result, the HCF for 56 and 84 is 7 × 2 × 2 = 28.

HCF of Two Numbers by Division Method

Follow the instructions below to calculate the HCF of two numbers using the division method.

Subtract the larger from the smaller.

Do the long division again, using the remainder of the previous step as the divisor and the dividend from the previous step as the dividend.

Long divide the remainder till it equals 0.

When remainder = 0, HCF is the last divisor left.

The prime factorization method is used to determine the highest common factor.

Step I:

Determine each number’s prime factorization.

Step II:

The HCF of the supplied numbers is calculated by multiplying all common prime factors together.

1. Using prime factorization, get the highest common factor (HCF) of 14 and 8.

Solution:

14 = 1 × 2 × 7. 

8 = 1 × 2 × 2 × 2. 

Common factors of 8 and 14 = 1 and 2. 

H.C.F. is the product of lowest powers of factors common to all numbers.

Highest common factor of 8 and 14 = 2.

2. Find highest common factor (HCF) of 9 and 27 by using prime factorization method.

Solution:

9 = 1 × 3 × 3.

27 = 1 × 3 × 3 × 3.

Common factors of 9 and 27 = 1, 3 and 3.

Highest common factor of 9 and 27 = 3 × 3 = 9.

Conclusion 

HCF splits two numbers evenly, leaving no residue. Each of the numbers in the HCF of two numbers is a factor. The HCF of two numbers is always less than or equal to each. When two prime numbers are multiplied together, the HCF is always 1.

The listed factors approach can be used to calculate the HCF of two numbers. We enumerate all the factors of two numbers and find the one with the highest common factor using this procedure.