Application of LCM (Lowest Common Multiple) in solving Quantitative Aptitude Problems

Saturday, February 20th, 2016


Basic Concepts for CAT Preparation
While most students are comfortable with the concept of HCF (Highest Common Factor) and LCM (Lowest Common Multiple), they somehow fail to apply it when required. Sometimes, they do not even realise that it needs to be applied. I sometimes feel sad when students ask me, “Sir, when to apply HCF and when to apply LCM?”. This question is a symbol of everything that is wrong with rote learning. HCF and LCM are concepts that students start learning as early as the 5th class in school (may be even earlier in some cases). The problem occurs because a few of them forget how the concepts need to be applied. The more common reason for the same, I believe, is because they learn the formula and then hope that they are using the right one when required. 

I will try to answer the question, “When to apply HCF and when to apply LCM?”. Think of the mathematical problem that you have in front of you as a house of bricks. Now imagine the stage in the problem that you are at is the level when walls are ready. If you are looking to find out something related to bricks, then you are probably looking at the HCF. If you are looking at the house, then you are probably looking at the LCM. In case you are not comfortable with metaphors, if you are looking at the values which are bigger than the numbers given to you – go for LCM. If you are looking to find out values that are smaller than the given numbers, you start hunting for HCF. This is under the assumption that you have figured out that one of them needs to be used. 

Let us now try and discuss some problems that use the concept of LCM in Quantitative Aptitude. 

Online CAT Coaching  Share on Facebook

The LCM of 1, 2, 3, … 60 is N. What is the LCM of 1, 2, 3, … 65?
We are given LCM (1, 2, 3 … 60) = n
Now, we need to find out LCM (1, 2, 3… 65)

= LCM (n, 61, 62, 63, 64, 65)
{The first 60 numbers can be replaced with ‘n’ as we already know their LCM}

= LCM (n, 61,64)
{62, 63, and 65 can be broken down into prime factors which are in turn factors of n}

= 61*2*n
{61 is a prime number. 64 is 2^6. 2^5 occurs in 32. An extra 2 is required to accommodate it}

= 122n

What is the unit digit of LCM of (13^501 – 1) and (13^501 + 1)?
13^501 – 1 and 13^501 + 1 are two consecutive even numbers.
One of them will be of the format 4k and the other one will be of the format 4k + 2.
They will only have 2 as a common factor.
=> HCF (13^501 – 1, 13^501 + 1) = 2

We also know that HCF*LCM = Product of two numbers
=> LCM = (13^501 – 1)(13^501 + 1)/2 = (13^1002 – 1)/2

Now, let’s try and find out the last digit of the LCM
Last digit of 13^1002
= Last digit of 3^1002
= Last digit of 3^(4k + 2)
= 9

Last digit of 13^1002 – 1 = 9 – 1 = 8
Last digit of (13^1002 – 1)/2 = 8/2 = 4

Given two arithmetic sequences and different ranges for the two sequences, how many numbers are common within these ranges?
Let us say that the two Arithmetic Progressions are:
AP(1) = a, a + d, a + 2d, a + 3d …
AP(2) = a’, a’ + d’, a’ + 2d’, a’ + 3d’ …

Now, we first need to find out a term which is common to both AP(1) and AP(2). That will be the first common term.
All common terms will be in an Arithmetic Progression. The common difference for them will be the LCM (d, d’)

Now, once you have the common terms (they are in an AP), you can find out number of terms in them by using the formula
(Last term – First term)/(Common Difference) + 1

Online CAT Coaching  Share on Facebook

What is the least number that when divided by 3,5,6,8,10 and 12 leaves a remainder of 2 but when divided by 13 leaves no remainder?
Suppose we are given that a number when divided by x, y, and z, leaves a remainder of a, b, and c; then the number will be of the format of LCM(x,y,z)*n + constant

The key in these questions is finding out the value of ‘constant’. If all of them leave the same remainder ‘r’, constant = r. It can also be looked at as the smallest number satisfying the given property.

So, the number N = LCM(3,5,6,8,10,12)*n + 2 = 120n + 2

Now we have to find out a suitable value of n such that 120n + 2 is divisible by 13.
We know that 117 is divisible by 13.
So, we need to find such a value of n such that 3n + 2 is divisible by 13.
That happens when n = 8
=> N = 120*8 + 2 = 962

What is a number that when divided by 10 leaves a remainder 9 and when divided by 9 then leaves a remainder 8 and similarly till 1?
Suppose we are given that a number when divided by x, y, and z, leaves a remainder of a, b, and c; then the number will be of the format of
LCM(x,y,z)*n + constant

The key in these questions is finding out the value of ‘constant’. If all of them leave the same remainder ‘r’, constant = r. It can also be looked at as the smallest number satisfying the given property.

We are given that the remainder from 10, 9, 8, 7…. and so on is 9, 8, 7, 6… and so on. That is the same as getting a remainder of -1 in all these cases.

N = LCM(10,9,8,7,6…)n – 1 = 2520n – 1

What is the greatest two-digit number that gives the remainder 5 when divided by 2, 3 or 4?
Suppose we are given that a number when divided by x, y, and z, leaves a remainder r; then the number will be of the format of
LCM(x,y,z)*n + r

Here we are given that the number leaves a remainder of 5 when divided by 2,3, and 4
=> Number will be of the format LCM(2,3,4)n + 5 = 12n + 5

Please note that we normally consider remainders from x in the range [0, x-1]. In this case a remainder of 5 from 4, is the same as remainder of 1 from 4.

The biggest two digit number of the format 12n + 5 will occur when n = 7
=> The biggest two digit number satisfying the property = 12*7 + 5 = 89

How do I find a number which when divided by 2, 3, 4, 5, 6, 7, 8, 9, 10 individually gives a remainder of 1 and when divided by 11 gives a remainder 0?
Suppose we are given that a number when divided by x, y, and z, leaves a remainder of a, b, and c; then the number will be of the format of
LCM(x,y,z)*n + constant

The key in these questions is finding out the value of ‘constant’. If all of them leave the same remainder ‘r’, constant = r. It can also be looked at as the smallest number satisfying the given property.

In this question, the number leaves a remainder of 1 from 2, 3, 4, 5, 6, 7, 8, 9, and 10.

So, the number N = LCM(2,3,4,5,6,7,8,9,10)*n + 1 = 2520n + 1
So, any number which is of the format of 2520n + 1 will satisfy the given conditions.
Some such numbers are 2521, 5041, 7561, …
We want to find such a number which follows the above rule and is still divisible by 11.

Rem[(2520n+1) / 11] = 0
=> Rem[(n+1) / 11] = 0 {Because 2519 is divisible by 11}
=> n = 10
=> N = 2520*10 + 1 = 25201 is our answer

Let me add 25201 is just one of such numbers. You can also put n as 21, 32,..

Find out a number which when divided by 7 leaves a remainder of 5, when divided by 6 leaves a remainder of 4, when divided by 5 leaves a remainder of 3, when divided by 4 leaves a remainder of 2, and when divided by 3 leaves a remainder of 1?
Suppose we are given that a number when divided by x, y, and z, leaves a remainder of a, b, and c; then the number will be of the format of
LCM(x,y,z)*n + constant

The key in these questions is finding out the value of ‘constant’. If all of them leave the same remainder ‘r’, constant = r. It can also be looked at as the smallest number satisfying the given property.

In this question, we are given
Remainder from 7 is 5
Remainder from 6 is 4
Remainder from 5 is 3
Remainder from 4 is 2
Remainder from 3 is 1

If you look at the negative remainders
Remainder from 7 is -2
Remainder from 6 is -2
Remainder from 5 is -2
Remainder from 4 is -2
Remainder from 3 is -2

So, the number N = LCM(7,6,5,4,3)*n – 2 = 420n – 2
So, any number which is of the format of 420n – 2 will satisfy the given conditions.
Some of these numbers are 418, 838, 1258….

Online CAT Coaching  Share on Facebook

What is the sum of all the integers less than 100 which leave a remainder 1 when divided by 3 and a remainder of 2 when divided by 4?
Suppose we are given that a number when divided by x, y, and z, leaves a remainder of a, b, and c; then the number will be of the format of
LCM(x,y,z)*n + constant

The key in these questions is finding out the value of ‘constant’. If all of them leave the same remainder ‘r’, constant = r. It can also be looked at as the smallest number satisfying the given property.

In this question, we are given
Remainder from 3 is 1
Remainder from 4 is 2

If you look at the negative remainders
Remainder from 3 is -2
Remainder from 4 is -2

So, the number N = LCM(3,4)*n – 2 = 12n – 2
So, any number which is of the format of 12n – 2 will satisfy the given conditions.
Positive Integers less than 100 which satisfy the above condition are
10, 22, 34… 94
Sum of these integers
= (No. of terms/2)*(First term + Last Term)
= (8/2)*(10 + 94) = 416

What is the largest three-digit number that when divided by 6 leaves a remainder of 5 and when divided by 5 leaves a remainder of 3?
Suppose we are given that a number when divided by x, y, and z, leaves a remainder of a, b, and c; then the number will be of the format of
LCM(x,y,z)*n + constant

The key in these questions is finding out the value of ‘constant’. If all of them leave the same remainder ‘r’, constant = r. It can also be looked at as the smallest number satisfying the given property.

In this question, we are given
Remainder from 6 is 5
Remainder from 5 is 3

So, the number N = LCM(6,5)*n + constant = 30n + constant
To figure out the constant, look at the numbers which give a remainder of 5 from 6.
They are 5, 11, 17, 23, 29….
Among these, find the one which leaves a remainder of 3 from 5. It is 23.

So, our number N should be of the format of 30n + 23

Biggest three digit number will occur when n is 32 = 30*32 + 23 = 983

What is the least multiple of 7, which when divided by 2, 3, 4, 5 and 6 leaves the remainders 1, 2, 3, 4 and 5 respectively?
Suppose we are given that a number when divided by x, y, and z, leaves a remainder of a, b, and c; then the number will be of the format of
LCM(x,y,z)*n + constant

The key in these questions is finding out the value of ‘constant’. If all of them leave the same remainder ‘r’, constant = r. It can also be looked at as the smallest number satisfying the given property.

In this question, we are given
Remainder from 2 is 1
Remainder from 3 is 2
Remainder from 4 is 3
Remainder from 5 is 4
Remainder from 6 is 5

If you look at the negative remainders
Remainder from 2 is -1
Remainder from 3 is -1
Remainder from 4 is -1
Remainder from 5 is -1
Remainder from 6 is -1

So, the number N = LCM(2,3,4,5,6)*n – 1 = 60n – 1
So, any number which is of the format of 60n – 1 will satisfy the given conditions.
Some such numbers are 59, 119, 179, 239….
We want the one which is divisible by 7.
59 is not divisible by 7
119 is divisible by 7 and our answer

What is the smallest number that when divided by 35, 36, and 91 leaves a remainder of 3?
Suppose we are given that a number when divided by x, y, and z, leaves a remainder of a, b, and c; then the number will be of the format of
LCM(x,y,z)*n + constant

The key in these questions is finding out the value of ‘constant’. If all of them leave the same remainder ‘r’, constant = r. It can also be looked at as the smallest number satisfying the given property.

In this question, we are given
Remainder from 35 is 3
Remainder from 36 is 3
Remainder from 91 is 3

So, the number N = LCM(35,36,91)*n + 3 = 16380n + 3
So, any number which is of the format of 16380n + 3 will satisfy the given conditions.
Smallest such number is 16380*0 + 3 = 3

Online CAT Coaching  Share on Facebook

Which is the smallest number which leaves remainder 8 and 12 when divided by 28 and 32 respectively?
Suppose we are given that a number when divided by x, y, and z, leaves a remainder of a, b, and c; then the number will be of the format of
LCM(x,y,z)*n + constant

The key in these questions is finding out the value of ‘constant’. If all of them leave the same remainder ‘r’, constant = r. It can also be looked at as the smallest number satisfying the given property.

In this question, we are given
Remainder from 28 is 8
Remainder from 32 is 12

If you look at the negative remainders
Remainder from 28 is -20
Remainder from 32 is -20
So, the number N = LCM(28,32)*n – 20 = 224n -20
So, any number which is of the format of 224n – 20 will satisfy the given conditions.
Smallest such number is 224*1 – 20 = 204

What is the least possible number which when divided by 18, 35, or 42 leaves 2, 19, 26 as the remainders respectively?
Suppose we are given that a number when divided by x, y, and z, leaves a remainder of a, b, and c; then the number will be of the format of
LCM(x,y,z)*n + constant

The key in these questions is finding out the value of ‘constant’. If all of them leave the same remainder ‘r’, constant = r. It can also be looked at as the smallest number satisfying the given property.

In this question, we are given
Remainder from 18 is 2
Remainder from 35 is 19
Remainder from 42 is 26

If you look at the negative remainders
Remainder from 18 is -16
Remainder from 35 is -16
Remainder from 42 is -16

So, the number N = LCM(18,35,42)*n – 16 = 630n – 16
So, any number which is of the format of 630n – 16 will satisfy the given conditions.
Least possible number would occur when n = 1
Least possible number will be 630 – 16 = 614

A number when divide by 16 leaves 6 remainder, when divided by 17, leaves 7 remainder and when divided by 18 leaves 8 remainder. ID the number is N. Then what will be the remainder when M, where M=N^2 +6N+16 is divided by 12?
The key in these questions is finding out the value of ‘constant’. If all of them leave the same remainder ‘r’, constant = r. It can also be looked at as the smallest number satisfying the given property.

In this question, we are given
Remainder from 16 is 6
Remainder from 17 is 7
Remainder from 18 is 8

If you look at the negative remainders
Remainder from 16 is -10
Remainder from 17 is -10
Remainder from 18 is -10

So, the number N = LCM(16,17,18)*n – 10 = 2448n – 10
So, any number which is of the format of 2248n – 10 will satisfy the given conditions.

Now, we need to find out the remainder of M = N^2 + 6n + 16 from 12
Rem[N^2/12] = Rem [(2448n – 10)^2/12] = Rem [(-10)^2/12] = 4
Rem[6n/12] = Rem [6(2448n – 10)/12] = Rem [-60/12] = 0
Rem[16/12] = 4

Remainder [M/12] = 4 + 0 + 4 = 8

With this, I would like to wrap up this post on Lowest Common Multiple and its applications. If you liked it, please share it on Facebook with your friends.

Cheers,
Ravi Handa,
Founder & Mentor,
Handa Ka Funda

Application of LCM (Lowest Common Multiple) in solving Quantitative Aptitude Problems
4.1 (81.6%) 25 votes

If you Like this post then share it!


Leave a Reply

Your email address will not be published. Required fields are marked *