# Finding largest number with GCD.

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.

• You want the LCM, not the GCD here Aug 4 '18 at 13:59

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

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

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.

• 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? Aug 4 '18 at 14:10
• @BravoJades See the edit. Aug 4 '18 at 15:26

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.