Suppose we have a number *X*, and we need to find the modulus of it with *N* numbers, *A*_{1}, *A*_{2}, ..., *A*_{N}.

Then is it true that if we know the modulus of *X* when divided by *LCM*(*A*_{1}, *A*_{2}, ..., *A*_{N}), then we can know the individual remainders when *X* is divided by these numbers (*A*_{1}, *A*_{2}, ..., *A*_{N}).

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.

Can you share the link to the editorial and the problem of the editorial?

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

Xwitha_{1},a_{2},a_{3}, ...,a_{n}, then we can know the remainder ofXwithLCM(a_{1},a_{2}, ...,a_{n})?That inverse is known as the Chinese remainder theorem.