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)
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
is it necessary that bi has to be an integer or can it fractional too ?
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.
If sum exceeds M you should take it modulo M.
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
Second one.