HCF and LCM

Navigation:-
Home -> Number Theory -> HCF and LCM

Prime factorisation
A prime factorisation of a natural number can be expressed in the exponential form.
For example:(i) 48 = 2 x 2 x 2x 2 x3 = 24 x 3(ii) 420 = 2 x 2 x 3 x 5 x 7 = 22 x 3 x 5 x 7

Least Common Multiple (L.C.M.):
A common multiple is a number that is a multiple of two or more numbers. The common multiples of 3 and 4 are 0, 12, 24, ....

The least common multiple (LCM) of two numbers is the smallest number (not zero) that is a multiple of both.

Method 1:
Simply list the multiples of each number (multiply by 2, 3, 4, etc.) then look for the smallest number that appears in each list.
Example: Find the least common multiple for 5, 6, and 15.
Multiples of 5 are 10, 15, 20, 25, 30, 35, 40,...
Multiples of 6 are 12, 18, 24, 30, 36, 42, 48,...
Multiples of 15 are 30, 45, 60, 75, 90,....
Now, when you look at the list of multiples, you can see that 30 is the smallest number that appears in each list.Therefore, the least common multiple of 5, 6 and 15 is 30.

Method 2
To use this method factor each of the numbers into primes. Then for each different prime number in all of the factorizations, do the following...
1. Count the number of times each prime number appears in each of the factorizations.
2. For each prime number, take the largest of these counts.
3. Write down that prime number as many times as you counted for it in step 2.
The least common multiple is the product of all the prime numbers written down.

Example: Find the least common multiple of 5, 6 and 15.
Factor into primes
Prime factorization of 5 is 5
Prime factorization of 6 is 2 x 3
Prime factorization of 15 is 3 x 5
· Notice that the different primes are 2, 3 and 5.
Now, we do
Step #1 - Count the number of times each prime number appears in each of the factorizations...
The count of primes in 5 is one 5
The count of primes in 6 is one 2 and one 3
The count of primes in 15 is one 3 and one 5

Step #2 - For each prime number, take the largest of these counts. So we have...
The largest count of 2s is one
The largest count of 3s is one
The largest count of 5s is one

Step #3 - Since we now know the count of each prime number, you simply - write down that prime number as many times as you counted for it in step 2.
Here they are...2, 3, 5

Step #4 - The least common multiple is the product of all the prime numbers written down.
2 x 3 x 5 = 30 Therefore, the least common multiple of 5, 6 and 15 is 30.
So there you have it. A quick and easy method for finding least common multiples.

Highest Common Factor (abbreviated H.C.F.) :
HCF 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.)

Example. Find the H.C.F. of 72, 126 and 270.
Solution. Using Prime factorisation
72 = 2 x 2 x 2 x 3 x 3 = 2 ^3 x 3 ^2
126 = 2 x 3 x 3 x 7 = 2 ^ 1 x 3 ^2 x 7 ^1
270 = 2 x 3 x 3 x 3 x 5 =2 ^1 x 3 ^3 x 5 ^1

H.C.F. of the given numbers = the product of common factors with least index= 2 ^1 x 3 ^2

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 = 18Similarly calculate H.C.F. of 18 and 270 as 18Hence H.C.F. of the given three numbers = 18

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.

Important

For LCM
1. LCM >= the largest number of a set.
2. For Co-prime numbers - LCM is product of co-prime numbers.
3. LCM is multiple of all the numbers of a set as well as HCF of a set of numbers.

For HCF
1. HCF =< the largest number of a set.
2. For Co-prime numbers - HCF is equals to 1.
3. HCF is factor of all the numbers of a set as well as LCM of a set of numbers.