HCF and LCM in CAT: Concepts, Shortcut methods, Practice Questions and Previous Year Questions

The two main methods which are used to find the LCM (Least Common Multiple) and the HCF (Highest Common Factor) of the numbers are Prime Factorization Method and Division Method.

LCM stands for Lowest Common Multiple where in the least or smallest common multiple of any two or more given natural numbers which is coined as LCM. Ex: LCM of 10, 15, and 20 is 60.

HCF stands for Highest Common Factor where in the largest or greatest factor common to any two or more given natural numbers is termed as HCF of given numbers. Ex: HCF of 4, 6 and 8 is 2.

---

Formula for LCM and HCF

[Click Here for Sample Questions]

The formula used for calculating the LCM and HCF for the given numbers:

Rule 1: HCF for two or more fractions is given by: HCF of NumeratorsLCM of Denominators

Rule 2: LCM for two or more fractions is given by: LCM of NumeratorsHCF of Denominators

Rule 3: If the HCF of x and y is G, then the HCF of

1. x, (x + y) is also G
2. x, (x - y) is also G
3. (x - y), (x + y) is also G

---

Short Cuts and Tricks and Tips for finding LCM

The methods which are used to find out the least common multiple of two numbers are:

1. LCM by Listing Method
2. LCM by Prime Factorization Method
3. LCM using Division Method

---

LCM by Listing Method

[Click Here for Sample Questions]

The 1st method wherein we can find out the common multiples of two or more numbers by listing their multiples. And out of these common multiples and the least common multiple is considered to be the LCM of two given numbers.

Follow the steps below to calculate the LCM of the two numbers A and B by the listing method:

1. First, list down first few multiples of A and B.
2. Mark the common multiples from the multiples of both numbers.
3. Select the smallest marked common multiple. Hence, this results in the LCM (A, B).

Find LCM of two positive integers 3 and 6.

Solution:

Multiples of 3: 3,6,9,12,15…

Multiples of 6: 6,12,18,24, 30…

The common multiples of 3 and 6 are 6, 12…, So, the least common multiple is 12.

Hence, LCM (3, 6) = 6

---

LCM by Division Method:

[Click Here for Sample Questions]

The 2nd method wherein we can find LCM using Prime factorization method of the given numbers. This can be done by dividing the numbers by a common prime number, and these prime factors are used to calculate the LCM of those numbers.

Follow the steps below to calculate the LCM of the two numbers A and B by Division Method:

First, find a prime number which is a factor of at least one of the given numbers. Write this prime number on the left of the given numbers.

If the prime number in step 1 is a factor of the number, then divide the number by the prime and write the quotient below it. If the prime number in step 1 is not a factor of the number, then write the number in the row below as it is. Continue the steps until 1 is left in the last row.

Example:

Let’s take two positive integers 6 and 2, the task is to find the LCM (6, 2).

Solution:

2 6, 2

3 3, 1

3 1. 1

LCM (6,2) = 2 * 3 * 3 = 18

The LCM is the product of all these prime numbers.

Hence, LCM (6, 2) = 18

---

LCM by Prime Factorization Method:

[Click Here for Sample Questions]

The 3rd method wherein we can find LCM using Prime factorization method of the given numbers.

Follow the steps below to calculate the LCM of two numbers using the prime factorization method:

First, find the prime factors of the given numbers using repeated division method.

Write these numbers in the form of exponent and find the product of only those prime factors that have the highest power.

The product of these factors with the highest powers is the LCM of the given numbers

Example:

Find LCM of two positive integers 120 and 300.

Solution:

The prime factorization of 120 are: 2*2*2*3*5 = 23*31*51

The prime factorization of 300 are: 2*2*3*5*5 = 22*31*52

Now, find the product of only those factors that have the highest powers among these. This will be, 23 * 31 * 52 = 8 * 3 * 25 = 600

Hence, LCM (120, 300) = 600

---

Tricks and Tips for finding LCM

1. Find the standard form of the numbers n1 and n2.
2. Write out all the prime factors , which are contained in the standard forms of either of the numbers.
3. Raise each of the prime factors listed to the highest of the powers in which it appears in the standard forms f the numbers n1 and n2.
4. The product of the results of the previous step will be the LCM of n1 and n2.

Ex: 1 Find the LCM of 150, 210, 375

Applying the above tricks and tips:

Step 1: Writing down the standard form of numbers:

150 = 5 x 5 x 3 x 2

210 = 5 x 2 x 7 x 3

375 = 5 x 5 x 5 x 3

Step 2: Writing down the prime factors that appears at least once in any of the numbers: 2x 3 x 5 x 7

Step 3: Raise each of the prime factors to their highest available power (considering each to the numbers) i.e. 2x 3 x 5 x 7 = 5250

Step 4: Hence, the LCM will be 21 x 31 x 53 x 71 = 5250

Important rule: GCD (n1. n2) LCM (n1. n2) = n1 . n2

The product of HCF and LCM is equals product of numbers.

---

Short Cuts for finding HCF

The methods which are used to find out the least common multiple of two numbers are:

1. HCF by listing factors method
2. HCF by prime factorization
3. HCF by division method

---

HCF by Listing Factors Method

[Click Here for Sample Questions]

The 1st method wherein we list the factors of each number and find the common factors of those numbers. Then, among the common factors, we determine the highest common factor.

Example:

Find the HCF of 15 and 30.

Solution: First, list down the factors of 15 and 30.

The factors of 15 are: 1, 3, 5, 15

The factors of 30 are: 1, 2, 3, 5, 10

We can see that 1, 2 are the only common factors of 15 and 30. Whereas 5 is the greatest among all the common factors.

Hence, HCF of 30 and 15 is 5.

---

HCF by Prime Factorization

[Click Here for Sample Questions]

The 2nd method wherein we can find HCF using Prime factorization method of the given numbers.

Follow the steps below to calculate the HCF of given numbers using the prime factorization method:

First, Find the common prime factors of the given numbers.

Multiply these common prime factors to obtain the HCF of those numbers.

Example:

Find the HCF of 80 and 90.

Solution:

The prime factors of 80: 2 * 2 * 2 * 2 * 5;

The prime factors of 90: 2 * 3 * 3 * 5.

We can see that 2, 5 are the only common factors of 80 and 90, Now, the HCF of 80 and 90 will be the product of the common prime factors, which are 2 and 5.

Hence, HCF of 80 and 90 is 10.

---

HCF by Division Method

[Click Here for Sample Questions]

The 3rd method where in HCF of two numbers can be calculated using the division method.

Follow the steps below to calculate the HCF of given numbers using the Division Method

First, we divide the larger number by the smaller number and check the remainder.

Then, make the remainder of the previous step as the new divisor and the divisor of the previous step becomes the new dividend. After this we perform the long division again.

Continue the long division process till we get the remainder as 0. It should be noted that the last divisor will be the HCF of those two numbers.

Example:

Find the HCF of 30 and 42.

 

---

Tricks and Tips for finding HCF or GCD

1. Find the standard form of the numbers n1 and n2.
2. Write out all the prime factors that are common to the standard forms of the number n1 and n2.
3. Raise each of the common prime factors listed above to the lesser of the powers in which it appears in the standard forms of the number n1 and n2.
4. The product of the results of the previous step will be the GCD of n1 and n2.

Ex: 1 Find the GCD of 150, 210, 375

Applying the above tricks and tips:

Step 1: Writing down the standard form of numbers:

150 = 5 x 5 x 3 x 2

210 = 5 x 2 x 7 x 3

375 = 5 x 5 x 5 x 3

Step 2: Writing down the prime factor which are common to all three numbers is 51 x 31

Step 3: This will give the same result i.e. 51 x 31

Step 4: Hence, the HCF will be 5 x 3 = 15