Prime Factorization Of HCF And LCM

Using Prime Factorization Methods to Find HCF and LCM

A factor is a number which divides a number exactly into a different number. For example, 5 divides 35 into 7, hence 5 is a factor of 35, while 7 is also a factor of 35. One is a factor of every number. The number itself is also a factor of any number.
Factorization is the method of writing a number as a product of several of its factors. Factorization is not considered meaningful as compared to division, but it finds its use when we wish to find the simplest constituents of a number and to represent a number as a product of the same.

Ancient Greek mathematicians first considered factorization in the case of integers. They are also responsible for proving the fundamental theorem of arithmetic, which says that every positive integer may be factored into a product of its constituent prime numbers, such that the constituent prime numbers cannot be further factored into integers greater than one. Generally, when we factor a number, we write the smallest factors first.

For example : Factors of 45 are : 1, 3, 5, 9, 15, 45

So, if we factorize 45, we get : 45 = 1 × 45, 45 = 3 × 15 and 45 = 5 × 9,

Prime Factorizations:

A prime factor is a number which cannot be divided perfectly by any other number that one and the number itself. Examples for prime factors are 3, 7, 19, 97 etc. 2 is the lowest prime number, as 1 is no considered a prime number. 2 is also the only even prime number. The greatest known prime number currently is  282,589,933 − 1, a number with 24,862,048 digits.

When we are dividing a number into its constituent numbers, we can write it as only a multiple of prime factors. This method of writing a number as a product of its constituent factors is prime factorization.

Example : 45 = 3 × 15
         45 =3 × 3 × 5
         45 = 32 × 5
         66 = 2 × 33
         66 = 2 × 3 × 11

Prime factorization is commonly used to break down a number into its constituent numbers to facilitate easy grouping, identification and classification.

Highest Common Factor (HCH) and Lowest Common Multiple (LCM) :

Highest Common Factor (HCF) :

The Highest Common Factor or HCF (also sometimes referred to as Greatest Common Divisor or GCD) is the highest factor which is common in a comparison between two or more given numbers. This means that the HCF of two numbers is the highest number which exactly divides two or more numbers.

Example: Considering the numbers 24 and 36, 12 is the HCF since it is the highest number that divides both 24 and 36.
Example: Considering the numbers 45, 60 and 90, the HCF is 15 since it is the highest number that divides 45, 60 and 90.

Lowest Common Multiple (LCM) :

The Lowest Common Multiple or LCM (also sometimes referred to as the Least Common Multiple) is the smallest positive number that is a multiple of two or more given numbers. In other words, it is the smallest number that the given numbers can be considered a factor.

Example: Considering the numbers 6, 10, and 12, the LCM is 60 since it is the lowest number which is a multiple of 6, 10, and 12.
Example: Considering the numbers 4, 10, and 16 the LCM is 80 since it is the lowest number which is a multiple of 4, 10, and 16.
If the given numbers do not have any common factor, then their LCM is simply the product of the given numbers.

Example: Find the LCM of 4, 5, and 7.
4, 5, and 7 have no common factors. Hence LCM is 4 × 5 × 7 = 140.

To find HCF using prime factorization:

Among the multiple methods to find HCF of two or more numbers, prime factorization method is one of them. We can separately find the prime factors of any numbers that are given and then find the HCF by identifying the common factors among them.

For example, the number 45 = 32 × 5 and the number 75 = 3 × 52
To find HCF, we need to find the common factors in each of the numbers.
In the above, the common factors are both 3 and 5.

3 is there twice in 45 and once in 75, while 5 is there once in 45 and twice in 75.
In case there are a different number of factors in the two numbers choose the minimum number of common factors in each case, which is one 3 and one 5

Therefore, HCF is 3 × 5 = 15.

Another example, the numbers 24 and 54, 24 = 23 ×3 while 56 = 23 × 7

To find HCF, we need to find the common factors in each of the numbers.

In the above, the common factor is 2.

The minimum number of common factor 2 on both sides is three.
Therefore, HCF is 23 = 8.

To find LCM using prime factorization:

Prime factorization is one of the methods to find the LCM of two or more numbers. We can similarly separately find the prime factors of any numbers that are given and then find the HLCM by identifying the common factors among them.

For example, the number 45 = 32 × 5 and the number 75 = 3 × 52

To find LCM, we need to multiply all the factors in each of the numbers.

In the above, the common factors are both 3 and 5. In case there are a different number of factors in each of the numbers, choose the maximum number of common factors in each case.

3 is there twice in 45 and once in 75, while 5 is there once in 45 and twice in 75.

Taking the maximum number of common factors in each case, which is two 3s and two 5s

Therefore, LCM is 32× 52 = 9 × 25 = 225.

Another example, the numbers 24 and 54, 24 = 23 ×3 while 56 = 23 × 7

To find LCM, we need to multiply all the factors in each of the numbers.

In the above, the factors are 2, 3, and 7.
The maximum number of the common factor 2 on both sides is three, while 7 and 3 are one.
Therefore, HCF is 23× 3 × 7 = 168.

Problems on HCF and LCM using prime factorization :


  • 1) Find the LCM and HCF of 112 and 96 using prime factorization method.

  • Solution: First find the prime factorization of the two numbers separately
    112 = 2 × 2 × 2 × 2 × 7
    112 = 24 ×7
    96 = 2 × 2 × 2 × 2 × 2 ×3
    96 = 25 × 3

    Then find HCF and LCM

    HCF: To find HCF, identify the common factors in the two numbers

    Here the common factor is 2

    Identify the minimum number of times 2 is multiplied in both the numbers
    Here 2 is multiplied 4 times in 112

    Therefore, HCF = 24 = 2 × 2 × 2 × 2 = 16

    LCM: To find LCM, identify all the factors in both the numbers.
    Here the factors are 2, 3, and 7.
    Identify the maximum number of times 2, 3, and 7 are multiplied in the two numbers.
    Here 2 is multiplied five times while 3 and 7 are multiplied once.

    Find the product of all the maximum number of each factor.

    Therefore, LCM = 25× 3 × 7= 2 × 2 × 2 × 2 × 2 × 3 × 7 = 672.

  • 2) Find the LCM and HCF of 480 and 620 using prime factorization method.

  • Solution: First find the prime factorization of the two numbers separately
    620 = 2 × 2 ×5 × 31
    620 = 22×5 × 31
    480 = 2 × 2 × 2 × 2 × 2 ×3× 5
    480 = 25 × 3× 5

    Then find HCF and LCM

    HCF: To find HCF, identify the common factors in the two numbers

    Here the common factor is 2

    Identify the minimum number of times 2 is multiplied in both the numbers

    Here 2 is multiplied 2 times in 620

    Therefore, HCF = 22= 2 × 2 = 4

    LCM: To find LCM, identify all the factors in both the numbers.

    Here the factors are 2, 3, 5, and 31.
    Identify the maximum number of times 2, 3, 5, and 31 are multiplied in the two numbers.

    Here 2 is multiplied five times while 3, 5, and 31 are multiplied once.

    Find the product of all the maximum number of each factor.

    Therefore, LCM = 25× 3 ×5 × 31= 2 × 2 × 2 × 2 × 2 × 3 ×5 × 31 = 14,880.