rhezo's blog

Math problem about divisibility and LCM [Solved]
By rhezo, history, 8 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

»
8 years ago, # |
  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
  • »
    »
    8 years ago, # ^ |
    ← 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
»
8 years ago, # |
  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
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Wow, thanks a lot!

    → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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)?

    → Reply