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.
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 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.