doubt in chinese remainder theoram

Revision en4, by _jarvis_, 2016-07-10 08:11:49

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)

Tags chinese remainder theo., simple math, doubt, modulus

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en4 English _jarvis_ 2016-07-10 08:11:49 13 Tiny change: 'answer is Yes**]\n\n2)w' -> 'answer is Integer only**]\n\n2)w'
en3 English _jarvis_ 2016-07-10 08:10:45 180
en2 English _jarvis_ 2016-07-10 07:15:45 51
en1 English _jarvis_ 2016-07-10 07:12:30 594 Initial revision (published)