Key Takeaways — Number Systems (Part III)

In our previous blog on number systems, we learnt about prime numbers, tests of divisibility and how to find number of zeroes in an expression or factorial. Today, we’ll learn about HCF and LCM which is one of the most important concepts in quantitative aptitude.

Basic Concepts

Factor is a number or quantity that when multiplied with another produces a given number or expression.
Multiple is a number that may be divided by another, a certain number of times without a remainder.
In other words, if a number a divides another number b exactly, we say that a is a factor of b and b is called the multiple of a.

Division Algorithm: Dividend = (Divisor * Quotient) + Remainder.

Concept of Highest Common Factor (HCF)

The HCF of two or more than two numbers is the greatest number that divides each of them exactly. HCF is also known as Greatest Common Divisor (GCD).

Consider two natural numbers a and b. If the numbers a and b are exactly divisible by the same number, say x, then x is a common divisor of a and b. The highest of all common divisors of a and b is called as HCF or GCD and is denoted as HCF(a, b).

Method to find HCF

• Factorization Method: Express all the given numbers as the product of prime factors. The product of the least powers of common prime factor gives HCF.
• Division Method: Suppose we have to find the HCF of two numbers. Divide the larger number by the smaller one. Now, divide the divisor by the remainder. Repeat the process of dividing the preceding number by the remainder last obtained till zero is obtained as remainder. The last divisor is the required HCF.
  Finding HCF of more than two numbers: Suppose we have to find the HCF of three numbers. Then, HCF of [(HCF of any two) and (3rd number)] gives HCF of the three given numbers.

Short-Cut Method to find HCF

Most of us would be knowing the above processes. But, these methods are time consuming. In aptitude tests and competitive examinations, you probably have around 1–2 minutes for each question.

Suppose you have to find the HCF of 39, 78 and 195.
Logic: The HCF of these numbers would necessarily have to be a factor of the difference between any pair of numbers.
So, the HCF has to be a factor of (78–39=39) as well as of (195–39=156) and (195–78=117).
Reason: For any number to be able to divide both the numbers, it can only do so if it is a factor of the difference between the two numbers.
Take the difference between the two closest numbers to reduce your calculations. In this case, 78–39=39.
The HCF has to be a factor of 39.
Note: Remember that whenever we have to find the list of factors for any number, we have to search for factors below the square root.
Factors of 39: 1, 3, 13, 39.
One of these numbers has to be the HCF. Since, we are trying to find the HCF, we begin with the highest number.
Divisibility by 39: 78 and 195 are divisible by 39.
Hence, 39 is the HCF of 39, 78, 195.

Concept of Least Common Multiple (LCM)

The least number which is exactly divisible by each one of the given numbers is called their LCM.

Let a and b be two natural numbers distinct from each other. The smallest natural number x that is exactly divisible by a and b is called the LCM and is denoted by LCM(a, b).

Method to find LCM

• Factorization Method: Resolve all the given numbers into a product of prime factors. Then, LCM is the product of highest powers of all the factors.
• Common Division Method: Arrange the given numbers in a row in any order. Divide by a number which divides exactly at least two of the given numbers and carry forward the numbers which are not divisible. Repeat the above process till no two of the numbers are divisible by the same number except 1. The product of the divisors and the undivided numbers is the required LCM of the given numbers.

Short-Cut Method to find LCM

The above methods for finding LCM are tedious and time-taking. We discussed about co-primes in our previous blog. By using the logic of co-primes, we can bypass the need to take the prime factors of all the numbers for which we are trying to find LCM.

Suppose you have to find the LCM of 9, 10, 12, 15.
Step 1: If you can see a set of 2 or more co-prime numbers in the set of numbers for which you are finding LCM — write down the multiplication of them.
In the above problem, 9 and 10 are co-primes (since two consecutive natural numbers are always co-prime). So, write down 9 * 10.
Step 2: For each of the other numbers, consider what part of them have already been taken into the answer and what part remains outside the answer.

• Prime factors of 12 = 2 * 2 * 3.
  Out of these, 9 * 10 already has a 3 and one 2 in its prime factors. But, one more 2 of number 12 hasn’t been considered. Hence, we need to add this 2 to our answer. Hence, the LCM now becomes 9 * 10 * 2.
• Prime factors of 15 = 3 * 5.
  9 * 10 * 2 has already taken into consideration 3 and 5. Hence, there is no need to add anything to our answer.

Thus, 9 * 10 * 2 is the LCM of 9, 10, 12, and 15.

Here’s how we used these strategies in Q 44 IBM Final Test.

Important properties of HCF and LCM

1. Product of two numbers = Product of their HCF and LCM.
2. Two number are said to be co-primes if their HCF is 1.
3. HCF of Fractions = HCF of Numerators / LCM of Denominators
4. LCM of Fractions = LCM of Numerators / HCF of Denominators

We have tried to cover most of the portion on number systems in the last 3 blogs. Study, practice and stay tuned for our upcoming blogs!

Click here to find more about our key takeaways which will help you solve aptitude questions in no time!

Please click that green heart below if you think others will find this helpful — thanks!

Follow our publication, by clicking on ‘follow’ button below, to get more updates!