Блог пользователя _jarvis_

Автор _jarvis_, история, 8 лет назад, По-английски

i tried to google regarding this doubt but there was no specific clarification, first i would state the theoram, then i will ask the doubt

Theoram

according to my understanding, chinese remainder theoram is stated as,

for some number x, if we want to find x % M,

where M = m1*m2....*mr , (all mi being relatively prime to each other)

then we may do it as,

if x = ai(mod mi)

then x%M = a1*b1*(M/m1) + ...... + ai*bi*(M/mi) + ...... + ar*br*(M/mr)

where bi*(M/mi) = 1(mod mi)

DOUBT

1)i just wanted to know that can bi be fractional or it has to an integer value ? [got cleared answer is Integer only]

2)what if the sum

a1*b1*(M/m1) + ...... + ai*bi*(M/mi) + ...... + ar*br*(M/mr)

exceeds M? (or are we sure it would always be less then M)

  • Проголосовать: нравится
  • -23
  • Проголосовать: не нравится

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

First, you need that for all i ≠ j. Or else you can't use the Chinese Remainder theorem. (there are some generalizations, but this is fine for now...)

Then bi is an integer value. Since by the above condition, (M / mi) is invertible so there exists an integer bi such that

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    is it necessary that bi has to be an integer or can it fractional too ?

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Integer. Everything here is integer arithmetic. Like is an integer, so how can the bi be fractional? You can interpret them as fractions mathematically, but for computational purposes, they should be integers.

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

If sum exceeds M you should take it modulo M.

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    i mean to ask, what exactly CRT states

    x%M = a1*b1*(M/m1) + ...... + ai*bi*(M/mi) + ...... + ar*br*(M/mr)

    OR

    x%M = ( a1*b1*(M/m1) + ...... + ai*bi*(M/mi) + ...... + ar*br*(M/mr) )%M