L.C.M. and H.C.F.

Prime factorisation

If a natural number is expressed as the product of prime numbers, then the factorisation of the number is called its prime (or complete) factorisation.

A prime factorisation of a natural number can be expressed in the exponential form.

For example:
(i) 48 = 2×2×2×2×3 = 24×3
(ii) 420 = 2×2×3×5×7 = 2² ×3×5×7.

Least Common Multiple (abbreviated L.C.M.) of two natural numbers is the smallest natural number which is a multiple of both the numbers.

Highest Common Factor (abbreviated H.C.F.) of two natural numbers is the largest common factor (or divisor) of the given natural numbers. In other words, H.C.F. is the greatest element of the set of common factors of the given numbers.

H.C.F. is also called Greatest Common Divisor (abbreviated G.C.D.)

Co-prime numbers: Two natural numbers are called co-prime numbers if they have no common factor other than 1.

In other words, two natural numbers are co-prime if their H.C.F. is 1.

Some examples of co-prime numbers are: 4, 9; 8, 21; 27, 50.

Relation between L.C.M. and H.C.F. of two natural numbers

The product of L.C.M. and H.C.F. of two natural numbers = the product of the numbers.

Note. In particular, if two natural numbers are co-prime then their L.C.M. = the product of the numbers.

Illustrative Examples

Example

Find the L.C.M. of 72, 240, 196.

Solution

Using Prime factorisation method
   72 = 2×2×2×3×3 = 2³×3²
   240 = 2×2×2×2×3×5 = 24×3×5
   196 = 2×2×7×7 = 2²×7²
L.C.M. of the given numbers = product of all the prime factors of each of the given number with greatest index of common prime factors
     = 24×3²×5×7² = 16×9×5×49 = 35280.

Using Division method
  2 | 72, 240, 196
  2 | 36, 120, 98
   2 | 18, 60 , 49
  3 | 9 , 30 , 49
      | 3  , 10 , 49
L.C.M. of the given numbers
    = product of divisors and the remaining numbers
    = 2×2×2×3×3×10×49
    = 72×10×49 = 35280.

Example

Find the H.C.F. of 72, 126 and 270.

Solution

Using Prime factorisation method
   72 = 2×2×2×3×3 = 2³×3²
  126 = 2×3×3×7 = 21×3²×71
  270 = 2×3×3×3×5 = 21×3³×51
H.C.F. of the given numbers = the product of common factors with least index
= 21×3² = 2×3×3 = 18

Using Division method
First find H.C.F. of 72 and 126
72|126|1
      72
       54| 72|1
              54
              18| 54| 3
                     54
                      0

H.C.F. of 72 and 126 = 18
Similarly calculate H.C.F. of 18 and 270 as 18
Hence H.C.F. of the given three numbers = 18

Exercise

Write the prime factorisation of the greatest 3-digit number.
Write the prime factorisation of the following numbers in exponential form:(i) 13860 (ii) 27830 (iii) 21952.
Find the smallest number which must be added to 9373 so that it becomes divisible by 4.
Find the smallest number which must be added to 605329 so that it becomes divisible by 9.
Replace the letter x in the number 8x516 by the smallest digit so that the number becomes divisible by 6.
Find the H.C.F. of:(i) 24, 60, 112 (ii) 70, 84, 336, 1260.
Find the least number which on adding 7 is exactly divisible by each of 15, 35 and 48.
Find the greatest number of four digits which is exactly divisible by each of 12, 18, 40 and 45.
Find the least number of five digits which is exactly divisible by each of 32, 36, 60, 90 and 144.
Find the H.C.F. of:(i) 72, 126, 168 (ii) 96, 528, 2160, 3520.
Find the greatest number that will divide 400, 435 and 541 leaving 9, 10 and 14 as remainders respectively.
Which of the following pairs of numbers are co-prime?(i) 15, 98 (ii) 198, 429 (iii) 847, 2160
If the product of two numbers is 84942 and their H.C.F. is 33, find their L.C.M.
The product of H.C.F. and L.C.M. of two numbers is 9072. If one of the numbers is 72, find the other number.
The H.C.F. and L.C.M. of two numbers are 12 and 5040 respectively If one of the numbers is 144, find the other number.

Answers

1. 999 = 3³×37
2. (i) 2²×3²×5×7×11    (ii) 2×5×11²×23
   (iii) 26×7³
3. 3           4. 2            5. 1             6. (i) 4   (ii) 14
7. 1673     8. 9720     9. 10080     10. (i) 6    (ii) 16       11. 17
12. (i) Co-prime           (ii) not co-prime           (iii) co-prime
13. 2574   14. 126       15. 420