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.
{"ft_lang_label":"__label__en","ft_lang_prob":0.942001,"math_prob":0.9987296,"size":483,"snap":"2022-05-2022-21","text_gpt3_token_len":125,"char_repetition_ratio":0.106471814,"word_repetition_ratio":0.0,"special_character_ratio":0.2836439,"punctuation_ratio":0.12727273,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.99986196,"pos_list":[0],"im_url_duplicate_count":[null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2022-01-22T11:24:56Z\",\"WARC-Record-ID\":\"<urn:uuid:09ca53c8-0fea-44ce-b2cd-4fced7b6406d>\",\"Content-Length\":\"153165\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:9634ffce-2043-4659-b207-b55850a61106>\",\"WARC-Concurrent-To\":\"<urn:uuid:e094e203-b428-4d95-9f8d-f97be6ec9b30>\",\"WARC-IP-Address\":\"151.101.129.69\",\"WARC-Target-URI\":\"https://math.stackexchange.com/questions/2871987/finding-largest-number-with-gcd\",\"WARC-Payload-Digest\":\"sha1:5IA2WRIT6VGP7I3ZINCVQKV6SXTQAJ24\",\"WARC-Block-Digest\":\"sha1:DDKOMV2GZGIPINNRBSLXSA6XWZIJKOQX\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2022/CC-MAIN-2022-05/CC-MAIN-2022-05_segments_1642320303845.33_warc_CC-MAIN-20220122103819-20220122133819-00144.warc.gz\"}"}