LCM & HCF

Lowest Common Multiple (LCM)

Highest Common Factor (HCF)

Greatest Common Divisor (GCD)

What is mean by HCF or GCD or GCM?

The greatest number which divides each of the two or more numbers is called HCF or Highest Common Factor. It is also called the Greatest Common Measure(GCM) and Greatest Common Divisor(GCD). HCM and LCM are two different methods, whereas LCM or Least Common Multiple is used to find the smallest common multiple of any two or more numbers.

How do you find the HCF?

There are three methods of finding H.C.F. of two or more numbers.

Division Method
Prime Factorization Method

1. H.C.F. by division method

Let us consider a few examples.

1. Find the HCF of 30 and 42.

Step I: Treat the smallest number i.e., 30 as divisor and the bigger number i.e., 42 as dividend.

Step II: The remainder 12 becomes the divisor and the divisor 30 becomes the dividend.

Step III: Repeat this process till the remainder becomes zero. The last divisor is the H.C.F.

2. Find the H.C.F. of 12 and 18.

Step I: First we consider the first two numbers and follow the same step 1, 2 and 3 of the above example.

Step II: The H.C.F. of the first two numbers which is 2 becomes the divisor and the third number 24 becomes the dividend. This process is repeated till the remainder becomes 0. H.C.F. is the last divisor.

3. Find the H.C.F. of 12 and 18.

Step I: Treat the smallest number i.e., 12 as divisor and the bigger number i.e., 18 as dividend.

Step II: The remainder 6 becomes the divisor and the divisor 12 becomes the dividend.

Step III: Repeat this process till the remainder becomes zero. The last divisor is the H.C.F.

2.Prime Factorization Method

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 Factorization

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 2^82,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 = 3²× 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.

1. Find highest common factor (HCF) of 14 and 8 by using prime factorization method.

Solution:

14 = 1 × 2 × 7.

8 = 1 × 2 × 2 × 2.

Common factor 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 factor of 9 and 27 = 1, 3 and 3.

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

3. Find highest common factor (HCF) of 6 and 16 by using prime factorization method.

Solution:

6 = 1 × 2 × 3.

16 = 1 × 2 × 2 × 2 × 2.

Common factor of 6 and 16 = 2.

Highest common factor of 6 and 16 = 2.

4. Find highest common factor (HCF) of 18 and 24 by using prime factorization method.

Solution:

18 = 1 × 2 × 3 × 3.

24 = 1 × 2 × 2 × 2 × 3.

Common factor of 18 and 24 = 1, 2, 3.

Highest common factor of 18 and 24 = 2 × 3 = 6.

5. Find highest common factor (HCF) of 12 and 56 by using prime factorization method.

Solution:

12 = 1 × 2 × 2 × 3.

56 = 1 × 2 × 2 × 2 × 7.

Common factor of 12 and 56 = 1, 2, 2.

Highest common factor of 12 and 56 = 2 × 2 = 4.

Page updated

Google Sites

Report abuse