1
$\begingroup$

The question is:

Find the largest number which when divided by 20,25,35 and 40 leaves a remainder of 14,19,29 and 34 respectively.

The solution is to find the difference which in this case is 20-14=6,25-19=6 and similarly for others.

Then finding GCD of all the numbers 20,25,35 and 40 and subtracting 6 from the obtained GCD.

I really did not understand why this solution works, if anyone could explain me the logic behind this in plain english. I am sorry I am weak in mathematics.

$\endgroup$
1
  • $\begingroup$ You want the LCM, not the GCD here $\endgroup$ Aug 4 '18 at 13:59
1
$\begingroup$

If $x$ is the required number, $x+6$ will be divisible by lcm$(20,25,35,40)$

$\endgroup$
2
  • $\begingroup$ Why with x+6? What is the logic? $\endgroup$ Aug 4 '18 at 13:40
  • $\begingroup$ @BravoJades, Observe that all remainders are $-6$ $\endgroup$ Aug 4 '18 at 14:33
1
$\begingroup$

First take the LCM of $20,25,35,40$ which is $1400$

Now, Since the $$20-6=14\\25-6=19\\35-6=29\\40-6=34$$So, $1400-6=1394$ will have the remainder of $14,19,29,34$ when divided by $20,25,35,40$

Edit:

Note that if a number is divided by $20$ then it leaves a remainder of $14$ and can be expressed as $20a-6$ or $20a+14$.

Similarly if the number gives remainders of $19,29,34$ when divided by $25,35,40$ respectively it can be expressed as $25b-6$ or $25b+19$ , $35c-6$ or $35c+29$ , $40d-6$ or $40d+34$.

We took $-6$ form because it is common among all the given $4$ divisors.

$\endgroup$
2
  • $\begingroup$ I do understand the procedure, but I am not quite getting the logic behind this, yes I a dumb, could you please please explain it elaborately? $\endgroup$ Aug 4 '18 at 14:10
  • $\begingroup$ @BravoJades See the edit. $\endgroup$
    – Key Flex
    Aug 4 '18 at 15:26
0
$\begingroup$

The question is flawed. There is no largest number like that, as you can add $\operatorname{LCM}(20,25,35,40)=1400$ to any solution and get a larger one.

The idea only works because you are asked for remainders that are the same amount below the moduli. If we asked for the smallest number greater than $0$ that was a multiple of $20,25,35,40$ you would answer with $\operatorname{LCM}(20,25,35,40)=1400$. Now we are asking for a number $6$ less than a multiple of each, so we subtract $6$. Another way to say the same thing is that $-6$ has the required remainders. As we said above, you can add $1400$ to any solution and get another, so we add $1400$ to $-6$ and get $1394$.

This is all based on the Chinese Remainder Theorem.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.