Aptitude - Problems on H.C.F and L.C.M - Discussion

Question :

Let N be the GREATEST number that will divide 1305, 4665 and 6905, leaving the SAME REMAINDER in each case. Then SUM of the digits in N is ____ .

Solution :

First we will find out N :

Use the formula :

Dividend = Divisor * Quotient + Remainder.

Given information :

1305 = N * x + Remainder ...equation 1.
4665 = N * y + Remainder ...equation 2.
6905 = N * z + Remainder ...equation 3.

Remainder in all the above three equations are equal but not known. Hence we eliminate them by performing subtraction as follows :

4665 - 1305 = N * (y-x) ...equation 2 - equation 1.
6905 - 4665 = N * (z-y) ...equation 3 - equation 2.
6905 - 1305 = N * (z-x) ...equation 3 - equation 1.

i.e.

3360 = N * (y-x) ...equation 4.
2240 = N * (z-y) ...equation 5.
5600 = N * (z-x) ...equation 6.

Values of x, y, z and N are not known. We are not concerned about values of x, y and z. From the equations 4, 5 and 6 it is clear N is a factor of 3360, 2240 and 5600. As the question states N is the GREATEST number, we will find out Highest Common Factor(HCF) of 3360, 2240 and 5600 which will be our N.

Factors :

3360 = 2*2*2*2*3*7*10.
2240 = 2*2*2*2*2*7*10.
5600 = 2*2*2*2*5*7*10.
HCF = 2*2*2*2*7*10 = 1120.

Hence N = 1120.

We have to find SUM of digits of N which is : 1+1+2+0 = 4.

Hence 4 is the answer(option A).

I took help of comments of @M.Harish, @Anchit and @Saraswati to provide the solution. A big thanks to them. The solution is meant to ease out the confusion regarding the question. I have tried to explain in detail hence its lengthy. Its recommended people solve the problem with as many shortcuts as possible in competitive exams where time is a constraint.

Let N be the greatest number that will divide 17, 41 and 77, leaving the same remainder in each case. Then the sum of the digits in N is:

It is easy to understand this with a simple example, and the logic behind this is so obvious.
Take number 12 (you can get any number you desire and practice it!).

Dividend = Divisor X Quotient + remainder (when the remainder is a constant!).

12 X 1 + 5 = 17.
12 X 3 + 5 = 41.
12 X 6 + 5 = 77.

Now, take the differences of 17, 41 and 77 in order considering the smallest, the middle and the largest numbers.

(41-17) = 24; (77-17) = 60; (77-41) =36.

Now take 24, 60, and 36 and find the HCF or HCD of these numbers: it is equal to 12.
Look at the "Divisor" used at the beginning. So, the divisor of that arrangement is equal to the HCF of 24, 60 and 36. When the remainder is constant, we can observe this pattern with any set of numbers arranged in this way.

The sum of digits of N = 1+2 =3.

1305, 4665, 6905 -----> These are the numbers.

In this question why we subtract the numbers because here, it is said that they have the same remainder.

So, 1305 = hcf * x + remainder -----> (1),

4665 = hcf * y + remainder -----> (2),

6905 = hcf * z + remainder -----> (3),

Where x, y, z are respective quotients.
Now we take (2) - (1).
3360 =hcf (y-x) -----> (4),
From (3) - (2) we have
2240 = hcf (z - y) -----> (5),
From(3) - (1) we have
5600 = hcf (z - x) -----> (6),
Now we can see from the equation (4), (5), (6) hcf of the three numbers is the hcf of the three numbers. So the hcf of 6905, 4665 and 1305 = hcf of the three numbers 5600, 3360, 2240 = 1120.

Given numbers 1305, 4665, 6905.

Now take difference;
4665-1305= 3360,
6905-4665=2240,
6905-1305=5600.

Take the smallest difference i.e 2240 find factors of it;
1-> 2240
2-> 1120
4-> 560
5-> 448
and so on;

Check from highest factors if any one of them leaves the same remainder for all given numbers
So, 1st one 2240 it can't divide 1305. So, go for the second one 1120.

1305÷1120 leaves 185 as the remainder
4665÷1120 leaves 185 as the remainder
6905÷1120 leaves 185 as the remainder.

As all given conditions fulfilled :)
We got it;
1120.
1+1+2+0= 4.
Edits are welcome

We subtracted 1305 from 4665, 4665 from 6905 and 1305 from 6905 because we needed n as a common factor which can be obtained this way.

Let us consider 1305 as q1
4665 as q2
And 6905 as we
Then,

4665-1305 = N(q2 -q1).
6905-4665 = N(q3-q2 ).
6905-1305 = N(q3-q2 ).

Now we get here N as the factor of all 3 digits and we need to find the greatest factor so, take out the HCF of all three numbers i.e 1305, 4665, 6905 = 1120.

And this is your answer if your question asks no. Of digits in the number simply add the digits i.e 1+1+2+0=4.

Hope this helped.

Let r be the remainder then the numbers (1305 - r) , (4665 - r) and (6905 - r) are exactly divisible by the required greatest number N.

We know that if two numbers are divisible by a certain number, then their difference is also divisible by that number.

Hence, the numbers.

(4665 - r) - (1305 - r) = (4665 - 1305),
(6905 - r) - (4665 - r) = (6905 - 4665),
(6905 - r) - (1305 - r) = (6905 - 1305).

They are divisible by the required number.

Therefore, the greatest number N = HCF of (4665 - 1305), (6905 - 4665) and (6905 - 1305).

Here taking difference is mentioned because we need to find h.c.f.

Here 1305=pq1+r;
4665=pq2+r;
6905=pq3+r;.here p is divident, q=quotient, r=reminder.

We want to find p so,
Totally 3 equations so,
P(q2-q1) = 3360.
p(q3-q2) = 2240.
p(q3-q1) = 5600 now there are 3 p's we need p that is h.c.f of (3360, 2240, 5600) here finding hcf by taking difference it will make easy now p = 1120 and (1+1+2+0) = 4.

Hope you all understood.

Impossible to calculate the GCD without successive difference:

a. 6905 - 4665.
b. 4665 - 1305.
c. 6905 - 1305.

Interestingly when you replace the values used in the above method to calculate the successive difference as illustrated below :

a. 6905 - 1305 (c above).
b. 6905 - 4665 (a above).
and
c. 4665 - 1305 (above it would replace the statement => 4665 - 1305).

It will convincingly still give rise to a G.C.D = 1120.

@Ramana : The Greatest common divisor (or the HCF) is not the solutiom needed here, it is rather the SUM OF THE DIGITS of THE HCF.


The Remainder being the same for each case, it is clear that subtracting the lesser no. from the greater ones renders the remainder zero. Also the HCF of te no.s left thereafter just wait to be known, because it perfectly divides the no.s and thus gets the same remainder in each case.

Any no. Can be represented as of the form D*q+r right. so we want remainder same in each case. So
1305=N*q1+r
4665=N*q2+r
6905=N*q3+r
Now, now subtracting 2 eq from 1 then ..3 to 2 then 3 to 1 we get N*(q2-q1)=3360.
Similarly, we will get the rest ones. now here, we just want the greatest no. Which divides all this num3360 2240 nd 5600 ....so simply take the hcf off all. We will get N=1120.

I hope this helps you.