rhezo's blog

Math problem about divisibility and LCM [Solved]
By rhezo, history, 10 years ago, In English

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.

  • Vote: I like it
  • +9
  • Vote: I do not like it

»
10 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    10 years ago, hide # ^ |
    ← Rev. 2  
    Vote: I like it 0 Vote: I do not like it

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

    → Reply
»
10 years ago, hide # |
 
Vote: I like it +4 Vote: I do not like it

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.

→ Reply