Chinese Remainder Theorem Calculator

The Chinese Remainder Theorem, often abbreviated CRT, combines several modular conditions into one solution. A congruence such as x ≡ 2 modulo 3 means that dividing x by 3 leaves remainder 2. This calculator accepts three such equations and finds the smallest nonnegative integer satisfying all of them simultaneously. The classical theorem applies when the moduli are pairwise coprime, meaning every pair has greatest common divisor one. Under that condition there is exactly one solution modulo the product of the moduli. For moduli 3, 5, and 7, the product is 105. If the smallest solution is 23, then 23, 128, 233, and every number obtained by adding or subtracting 105 satisfy the same system. The constructive algorithm begins by multiplying all moduli to form M. For each equation, it divides M by that equation's modulus to form a partial product. Because the moduli are pairwise coprime, the partial product has a modular multiplicative inverse relative to the omitted modulus. Multiplying each remainder, partial product, and inverse creates a term that matches one congruence while contributing zero to the others. Adding the terms and reducing modulo M yields the answer. CRT has applications far beyond textbook number theory. It supports efficient large-integer arithmetic, cryptographic implementations, coding theory, calendar cycles, rotating schedules, computer algebra, and the reconstruction of values from residues. It is particularly useful when a difficult calculation can be split into smaller independent calculations modulo several numbers and recombined afterward. Enter integer remainders and moduli greater than one. A remainder may be negative or larger than its modulus because reduction normalizes it automatically. This version intentionally requires pairwise coprime moduli, matching the standard theorem and guaranteeing a unique residue class. Systems with noncoprime moduli can sometimes be solved, but they require an additional compatibility check and are outside this calculator's scope. Always verify a result by dividing it by each modulus and checking the resulting remainder.