_jarvis_'s blog

By _jarvis_, history, 8 years ago, In English

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)

  • Vote: I like it
  • -23
  • Vote: I do not like it

| Write comment?
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

If sum exceeds M you should take it modulo M.

  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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