Home >  Term: Chinese remainder theorem
Chinese remainder theorem

An integer n can be solved uniquely mod LCM(A(i)), given modulii (n mod A(i)), A(i) > 0 for i=1..k, k > 0. In other words, given the remainders an integer gets when it's divided by an arbitrary set of divisors, you can uniquely determine the integer's remainder when it is divided by the least common multiple of those divisors.

For example, knowing the remainder of n when it's divided by 3 and the remainder when it's divided by 5 allows you to determine the remainder of n when it's divided by LCM(3,5) = 15.

0 0

Looja

  • GeorgeV
  •  (Gold) 1123 points
  • 100% positive feedback
© 2024 CSOFT International, Ltd.