Chinese Remainder Theorem
ModulusHardSolve systems of simultaneous congruences for pairwise coprime moduli.
Alt+Shift+C
Congruences (Enter 'a m' per line)
1
2
3
4
5
Complexity Indices
Time ComplexityO(K log M)
Auxiliary SpaceO(K)
Conceptual Overview
Chinese Remainder Theorem (CRT) states that if one knows the remainders of a division of an integer n by several pairwise coprime integers, then the remainder of the division of n by the product of these integers is uniquely determined.
Source: CP-Algorithms reference guide