Please subscribe to the official Codeforces channel in Telegram via the link https://t.me/codeforces_official. ×

### rhezo's blog

By rhezo, history, 7 years ago, 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. math, Comments (6)
 » Can you share the link to the editorial and the problem of the editorial?
•  » » 7 years ago, # ^ | ← Rev. 2 →   This is the link. It says " In fact, we need one remainder modulo LCM(1, 2, 3, …, 10) = 2520, to know remainder modulo each possible digit."
 » It's actually really simple, if you stop to think about what all of this means. If you know X % LCM = m, then X = LCM*c + m. But a1 divides LCM, so X = a1*k*c + m. Therefore, as the first part is divisible by a1, X % a1 = m % a1.
•  » » Wow, thanks a lot!
•  » » How can I prove the inverse? That is if we know the remainder of number X with a1, a2, a3, ..., an, then we can know the remainder of X with LCM(a1, a2, ..., an)?
•  » » » That inverse is known as the Chinese remainder theorem.