HCF and LCM Concepts

James Bond, a peon in a Government school, enters into a classroom. The teacher in the class asks him, "If there are 40 students in my class with 24 boys and 16 girls, I wish to divide boys and girls in different groups (no gender mixing), how should I do that?" James Bond says, "There are many ways of doing it". The teacher further states, "Every group should have the same number of students and I want to have the minimum number of groups". Now, James Bond got confused. He tries to find a number, which divides 24 and 16 i.e. he lists the factors (to learn how to find factors of a number click here) of 24 as 1, 2, 3, 4, 6, 8, 12, 24. Then he lists the factor of 16 as 1, 2, 4, 8, and 16.  Then he writes their common factors as 1, 2, 4, 8. He recalls that the teacher told him to keep the number of groups as low as possible. He could accomplish so by having maximum number of students in each group. From among the common factors, he finds the largest factor i.e. hcf of two numbers. That happens to be 8. As soon as he discloses the number of students i.e. 8, all the class students along with the teacher praise him.
What did James Bond do? First, he found the factors (F) of two numbers. Then he listed the common (C) factors of the two. After that the highest (H) factor out of the common factors was chosen and this common factor became the number of students in each group. This is basically the concept of highest common factor, which is popularly called as HCF.
Snap Web Banner
Greatest Common Divisor (GCD)/ Highest Common Factor (HCF)
The highest common factor of two or more numbers is the greatest common divisor, which divides each of those numbers an exact number of times. The process to find the HCF is
  1. Express the numbers given as a product of prime numbers separately i.e. finds factors of numbers
  2. Take the product of prime numbers common to both numbers
Illustration 1: Find the HCF of 1728 and 14.
Sol: The prime factorization of 1728 is 12 × 12× 12= 33x26.
The prime factorization of 14 is 2 × 7.
The common prime factor is 2. HCF = 2.
Illustration 2: Find the HCF of 27, 18 and 36.
Sol: Firstly find the prime factors of the numbers such as 27 = 3 × 3 × 3, 18 = 3 × 3 × 2 and
36 = 3 × 3 × 2 × 2, then take the common prime numbers, which are 3 & 3.
Now the product of these prime numbers i.e. 3 × 3 = 9 is the HCF of these two numbers.
Understanding LCM or Least Common Multiple
The least common multiple (LCM) of two or more numbers is the smallest of the numbers, which is exactly divisible by each of them, e.g. consider two numbers 18 and 24
The multiples of 18 are: 18, 36, 54, 72, 90, 108, 126, 144, 162, 180, 198, 216, ....
The multiples of 24 are: 24, 48, 72, 96, 120, 144, 168, 192, 216,......
The common multiples of both 18 and 24 are 72, 144, 216,....
The least common multiple is 72.
Here again try to break the words in reverse order and understand the concept. Firstly find the multiples of the numbers. Secondly, the common multiples of the numbers and finally the least out of those will be the LCM.
The process to find the LCM is
  1. Express the numbers given as a product of prime numbers separately i.e. finds factors of numbers
  2. Take the product of prime factors of the two numbers after eliminating repetition of the common factors.
Let us solve the above example with this method as well. The factorization of 18 is 2 × 3 × 3 and the factorization of 24 is 2 × 2 × 2 × 3. Now the only common factor is 2 × 3, which appears in both the numbers, thus it is to be taken only once while finding LCM. Thus LCM will be 2 × 2 × 2 × 3 × 3 = 72.
Alternatively, LCM is the product of all prime factors of the given numbers, the common factors among them being in their highest degree e.g. the LCM of 2x1y2z4 and 5x1y3z5 will be  = 10x1y3z5, where x, y and z are the prime factors.
Illustration 3: Find LCM of two numbers: 15 and 30.
LCM and HCF of Fractions:
LCM of fractions = LCM of numerators / HCF of denominators ; e.g. LCM of 2/5 and 3/10 = 6/5
HCF of fractions = HCF of numerators / LCM of denominators ; e.g. LCM of 2/5 and 3/10 = 1/10
bimtech