>  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

작성자

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