Please subscribe to the official Codeforces channel in Telegram via the link ×

Math problem about divisibility and LCM [Solved]

Revision en2, by rhezo, 2016-06-16 01:07:09

Suppose we have a number X, and we need to find the modulus of it with N numbers, A1, A2, ..., AN.

Then is it true that if we know the modulus of X when divided by LCM(A1, A2, ..., AN), then we can know the individual remainders when X is divided by these numbers (A1, A2, ..., AN).

Can anyone give me a proof? And also the method of how to find the individual remainders.

I read this on a editorial on HackerEarth.

Tags math, divisibility, lcm


  Rev. Lang. By When Δ Comment
en2 English rhezo 2016-06-16 01:07:09 9
en1 English rhezo 2016-06-15 23:30:58 487 Initial revision (published)