# Chinese Remainder Theorem Solver (System of Congruences)

Generalized pairwise-merge CRT for 2–20 congruences: coprime moduli give the product modulus, consistent non-coprime moduli give the lcm, inconsistent systems are rejected.

> Canonical page: https://elysiatools.com/en/tools/chinese-remainder-theorem

- **Category:** Math & Numbers

- **Keywords:** chinese remainder theorem, crt, congruence system, simultaneous congruences, modular arithmetic, lcm, number theory, sunzi

## Overview

The Chinese Remainder Theorem Solver calculates the unique integer solution for systems of 2 to 20 simultaneous congruences using generalized pairwise merging. It handles both pairwise coprime moduli and consistent non-coprime moduli by computing the least common multiple (LCM), while identifying and rejecting contradictory systems.

## Inputs

- **Remainders r (one per equation)** (text): Comma- or space-separated remainders, one per congruence; negative values are reduced mod m.
- **Moduli m (one per equation)** (text): Comma- or space-separated moduli (each m ≥ 2), matching the remainders count.

## When to use

- Solving classic modular arithmetic and number theory problems involving simultaneous remainder conditions.
- Merging non-coprime modular systems where consistency depends on greatest common divisor compatibility.
- Verifying step-by-step solutions for cryptography, modular scheduling, or discrete mathematics coursework.

## How it works

- Enter the list of remainders and corresponding moduli as comma- or space-separated values.
- The solver processes equations sequentially using pairwise merging to compute intermediate remainders and moduli.
- For coprime moduli, it combines them via their product; for non-coprime moduli, it verifies consistency using the greatest common divisor and combines them via the least common multiple.
- The tool outputs the unique solution x in the interval \[0, M) along with a verification check for each original congruence.

## Use cases

- Solving classical Chinese Remainder Theorem word problems from discrete mathematics and ancient puzzles.
- Determining periodic synchronization cycles when two or more cyclic events repeat with offset starting times.
- Validating modular arithmetic steps in RSA key operations and cryptographic congruence calculations.

## Frequently asked questions

### Can this tool solve congruences with non-coprime moduli?

Yes, it uses the generalized Chinese Remainder Theorem to find a solution modulo the LCM if the system is consistent.

### What happens if a system of congruences has no solution?

If the difference between remainders is not divisible by the greatest common divisor of their moduli, the solver identifies and rejects the system as inconsistent.

### Are negative remainders allowed as input?

Yes, negative remainders are automatically reduced modulo their respective modulus m before solving.

### What is the maximum number of congruences supported?

The solver supports systems containing between 2 and 20 simultaneous congruence equations.

### What is the minimum value required for each modulus?

Each modulus m must be an integer greater than or equal to 2.

## Related tools

- [Carmichael Function λ(n) Calculator](https://elysiatools.com/en/tools/carmichael-function): Group exponent λ(n) from prime factorization with φ(n) comparison, primitive-root existence, Korselt's Carmichael-number detection, and optional sample-unit verification.
- [Permutation / Combination / Subset Generator (With Repeats)](https://elysiatools.com/en/tools/combinatorial-generation): Deduplicated, lexicographic permutations / combinations / subsets of up to 12 items with exact multiset counts; display capped at 200 entries.
- [Euler Totient Function φ(n) Calculator](https://elysiatools.com/en/tools/euler-totient-function): Exact φ(n) from trial-division factorization (n ≤ 10¹²) with optional coprime listing and Euler's theorem recall.
- [Fraction Decimal Converter](https://elysiatools.com/en/tools/fraction-decimal-converter): Convert between fractions and decimals with support for mixed numbers, improper fractions, and various decimal formats
- [Zero-Sum Game Solver (Saddle Point / Linear Programming)](https://elysiatools.com/en/tools/game-theory-zero-sum): Two-person zero-sum games: saddle-point test first, then mixed strategies from a single-phase simplex LP with dual shadow prices, verified by security-level checks.
- [Inverse Laplace Transform Calculator (Partial Fractions)](https://elysiatools.com/en/tools/inverse-laplace-calculator): Partial-fraction inverse Laplace transform for proper rational functions: root factorization (real + conjugate pairs), exact coefficient system, term-by-term inversion.
- [Laplace Transform Calculator (Table Lookup)](https://elysiatools.com/en/tools/laplace-transform-calculator): Table lookup of L{f(t)} for 14 standard pairs, with parameter substitution, region of convergence, derivation note, and optional numeric F(s₀) evaluation.
- [Multiplicative Order Calculator mod n (ordₙ(a))](https://elysiatools.com/en/tools/order-of-element-mod-n): Smallest k with a^k ≡ 1 (mod n) via φ(n) reduction: power table, minimality proof, cyclic subgroup , primitive-root and maximal-order flags.

## Samples

- [NATS Message System Samples](https://elysiatools.com/en/samples/nats-samples): NATS messaging system examples including pub/sub, request-reply, queue groups, and JetStream for modern cloud-native applications
- [Web Image Processing Python Samples](https://elysiatools.com/en/samples/web-image-processing-python): Web Python image processing examples using PIL/Pillow including reading, saving, resizing, and format conversion
- [Chinese-English Mixed Text Samples](https://elysiatools.com/en/samples/text-chinese-english-mixed-samples): Sample text files with mixed Chinese and English content for testing automatic spacing tools
- [Text with Chinese Samples](https://elysiatools.com/en/samples/text-with-chinese-samples): Mixed language text containing Chinese characters for testing Chinese extraction