Prime Factorization, Highest Common Factor (HCF), Least Common Multiple (LCM)

Prime Numbers

A whole number greater than 1 that has only two factors, 1 and itself, is called a prime number.

For example, 2, 3, 5, 7, 11, 13, 17, 19, 23, etc. are all prime numbers.

Composite Numbers

A whole number greater than 1 that has more than two factors is called a composite number.

For example, 4, 6, 8, 9, 10, 12, 14, 15, etc. are all composite numbers.

     Co-primes

A pair of two natural numbers having no common factor other than 1 are called co-primes. The numbers may or may not be primes.

For example, (2, 3), (3, 5), (6, 35), (9, 16), (5, 12), etc.

       Twin Primes

Pairs of prime numbers that differ by 2 are called twin primes.

For example, (3, 5), (5, 7), (11, 13), (17, 19), (29, 31), etc.

        Prime Triplets

The set of three consecutive prime numbers, i.e. (3, 5, 7), (11, 13, 17), etc. are called prime triplets.

Prime Factorization

A prime number that is a factor of a composite number is called a prime factor of the composite number.

The process to express a composite number as a product of prime factors only is called prime factorization.

There are two methods two find the prime factorization of a composite number.

      1.      Factor Tree Method

      2.      Continuous Division Method

Factor Tree Method

Example 1: Find the prime factorization of 340.

Solution: We can construct a factor tree as follows.

Step 1: Write down two factors whose product is 340 as follows.

Step 2: Continue to factorize any factors which is a composite number.

Step 3: Stop this process when the last row of the tree shows only prime factors. The product of all the prime factors in the tree yields the prime factorization of the given number.

Therefore, 340 = 2 × 2 × 5 × 17

Continuous Division Method

We can also express 340 as a product of its prime factors using the continuous division method by dividing 340 by the smallest prime numbers such as 2, 3, 5, etc.

Therefore, 340 = 2 × 2 × 5 × 17

Highest Common Factor (HCF)

The highest common factor (HCF) of a group of numbers is the largest number that can divide all the numbers in the group.

For example, let us find the HCF of 18 and 24.

The factors of 18: 1, 2, 3, 6, 9, 18

The factors of 24: 1, 2, 3, 4, 6, 8, 12, 24

We can see that 1, 2, 3, and 6 are the common factors of 18 and 24. The largest of these common factors is 6. Thus, 6 is the highest common factor (HCF) of 18 and 24.

There are two methods to find the HCF of the given numbers.

      1.      Prime Factorization Method

      2.      Common Division Method

Prime Factorization Method

Example 2: Find the HCF of 750 and 225 using prime factorization.

Solution: We find the prime factorization of each number from any one of the given methods.

750 = 2 × 3 × 5 × 5 × 5

225 = 3 × 3 × 5 × 5

HCF = 3 × 5 × 5

          = 75

Common Division Method

Example 3: Find the HCF of 750 and 225 using common division method.

Solution: In this method, we start dividing by smallest prime factor of both the numbers and continue until both the numbers does not have any common prime factor. The product of all the common prime factors is the required HCF.

HCF = 3 × 5 × 5 = 75

Therefore, the HCF of 750 and 225 is 75.

Least Common Multiple (LCM)

The least common multiple (LCM) of a group of numbers is the smallest number which is divisible by all the numbers in the group.

For example, let us find the LCM of 6 and 8.

The multiples of 6: 6, 12, 18, 24, 30, 36, 42, 48, 54, 60, …

The multiples of 8: 8, 16, 24, 32, 40, 48, 56, 64, 72, 80, …

We can see that 24 and 48 are the first two common multiples of 6 and 8. Since 24 is the least of all the common multiples, we say that the least common multiple (LCM) of 6 and 8 is 24.

There are two methods to find the LCM of the given numbers.

      1.      Prime Factorization Method

      2.      Long Division Method

Prime Factorization Method

Example 4: Find the LCM of 20, 24, and 70 using prime factorization method.

Solution: We find the prime factorization of each number from any one of the given methods.

20 = 2 × 2 × 5

24 = 2 × 2 × 2 × 3

70 = 2 × 5 × 7

LCM = 2 × 2 × 2 × 3 × 5 × 7

          = 840

Therefore, the LCM of 20, 24 and 70 is 840.

Long Division Method

Example 5: Find the LCM of 24 and 90 using long division method.

Solution: In this method, we start dividing by smallest prime factor of one or both the numbers and continued dividing until you get 1. The product of all the divisors is the required LCM.

LCM = 2 × 2 × 2 × 3 × 3 × 5

          = 360

Therefore, the LCM of 24 and 90 is 360.

Relationship between HCF and LCM of Two Numbers 

Let us consider any two prime numbers. Their HCF is always 1, and LCM is equal to their product. For example, 5 and 7 are two prime numbers.

∴ LCM of 5 and 7 = 5 × 7 = 35

HCF of 5 and 7 = 1

Product of given numbers = 5 × 7 = 35

Also, product of HCF and LCM = 1 × 35 = 35

So, HCF × LCM = Product of given prime numbers

Let us consider any two composite numbers, say, 12 and 16.

HCF of 12 and 16 = 4

LCM of 12 and 16 = 48

Now, product of HCF and LCM = 4 × 48 = 192

Product of numbers = 12 × 16 = 192

∴ HCF × LCM = Product of given composite numbers

Example 6: The LCM of 16 and another number is 48. If their HCF is 8, find the other number.

Solution: Product of given numbers = LCM × HCF

∴ 16 × other number = 48 × 8

∴ other number = (48 × 8)/16 = 24

So, the other number is 24.

Example 7: The LCM and HCF of 60 and another number are 240 and 20 respectively. Find the other number.

Solution: Product of given numbers = LCM × HCF

∴ 60 × other number = 240 × 20

∴ other number = (240 × 20)/60 = 80

So, the other number is 80.

Example 8: The HCF of 25 and 70 is 5. Find their LCM.

Solution: Product of given numbers = LCM × HCF

∴ 25 × 70 = LCM × 5

∴ LCM = (25 × 70)/5 = 350

So, the LCM is 350.

 Study Divisibility Tests in detail ---- Click Here!