This Chinese remainder theorem calculator solves systems of simultaneous congruences — x ≡ a₁ (mod m₁), x ≡ a₂ (mod m₂), x ≡ a₃ (mod m₃) — returning the smallest non-negative solution and the full solution family, for pairwise coprime moduli.

–

Sunzi's Puzzle, Solved by Theorem

The oldest problem in this calculator's family is roughly 1,700 years old, from the Chinese text Sunzi Suanjing: a number leaves remainder 2 when counted by threes, 3 when counted by fives, 2 when counted by sevens — find it. The answer is 23, and the Chinese remainder theorem is the guarantee that such puzzles always work: when the moduli are pairwise coprime, a system x ≡ aᵢ (mod mᵢ) has exactly one solution modulo the product M = m₁m₂···mₖ. This calculator solves up to three congruences by incremental combination — solve two into a single congruence modulo their product (using the modular inverse from the extended Euclidean algorithm), then fold in the third — and returns the smallest non-negative solution plus the full family x ≡ x₀ (mod M): the default Sunzi system gives x = 23, period 105 (3 × 5 × 7), so 23, 128, 233, … all satisfy it. The verification line in the results re-checks every remainder, because in modular arithmetic an answer you haven't re-divided is a rumor.

CRT is load-bearing mathematics far beyond puzzles. RSA implementations perform private-key operations modulo p and modulo q separately and recombine via CRT, running about 4× faster than working modulo n = pq directly (the "CRT optimization" in every crypto library). Residue number systems — representing integers by their remainders modulo several small coprime moduli — let hardware perform addition and multiplication with no carries between channels, an idea that surfaces in DSP chips and fault-tolerant computing. Calendar and scheduling problems are CRT in civilian clothes: events repeating every 3, 5 and 7 days coincide every 105 days, and the offset of the next coincidence is exactly a remainder system. The coprimality condition is the whole ballgame: with moduli sharing factors, a solution exists only if the remainders agree modulo each shared gcd (x ≡ 1 mod 4 and x ≡ 3 mod 6 agree mod 2 and reconcile; x ≡ 1 mod 4 and x ≡ 2 mod 6 fight forever), and uniqueness then holds modulo the LCM rather than the product — the calculator checks coprimality and tells you plainly when the classic theorem doesn't apply.

Worked Examples (Verified)

  • Sunzi's classic: x ≡ 2 (mod 3), 3 (mod 5), 2 (mod 7) → x = 23 (mod 105).
  • Two congruences: x ≡ 1 (mod 4), x ≡ 2 (mod 5) → x = 17 (mod 20): 17 mod 4 = 1, 17 mod 5 = 2.
  • Egg-counting variant: x ≡ 1 (mod 2, 3, 4, 5, 6), x ≡ 0 (mod 7) → 301 (the ones-family runs 1, 61, 121, 181, 241, 301… by the LCM 60, and 301 is its first multiple of 7).
  • Next after 1,000: in the Sunzi family, 23 + 105 × 10 = 1,073 is the first solution above 1,000.

CRT Discipline

  • Check coprimality first: gcd of every modulus pair must be 1 for the classic theorem and its product period.
  • Reduce remainders into range (a mod m) before solving — a remainder of 8 mod 5 is 3, and feeding raw values invites confusion, not wrongness.
  • Non-coprime systems aren't automatically hopeless: they're solvable exactly when remainders agree modulo the gcds, with period = LCM — but that's the generalized theorem, a different tool.
  • Always verify the answer against every congruence — one modular-inverse slip corrupts everything downstream.
  • Bigger moduli multiply fast: the product period explodes combinatorially, which is a feature for cryptography and a trap for the unwary.

Related Tools

Frequently Asked Questions

How does the Chinese remainder theorem work?

For pairwise coprime moduli, the system x ≡ aᵢ (mod mᵢ) has a unique solution modulo M = m₁···mₖ. Constructively: combine two congruences at a time — find t with x₀ + M₁t ≡ a₂ (mod m₂) using the modular inverse of M₁ mod m₂ (from the extended Euclidean algorithm), update x, multiply the period — then fold in the next. This calculator runs that construction for up to three congruences and verifies the result against every remainder before presenting it.

What is the answer to the classic Sunzi problem?

23. Counted by threes it leaves 2, by fives 3, by sevens 2 — and the full solution family is 23 + 105k (105 = 3 × 5 × 7): 23, 128, 233, 338, … The problem appears in the Sunzi Suanjing (roughly 3rd–5th century CE) — Sunzi even gave the recipe ("multiply by 70, by 21, by 15, add, subtract multiples of 105"), which encodes the modular inverses 70 ≡ 1 (mod 3)-style basis numbers that the modern constructive proof still uses.

What if the moduli are not coprime?

Then the classic theorem stays silent and one of two things is true: the system is inconsistent (remainders disagree modulo some shared gcd — e.g., x ≡ 1 mod 4 forces odd, x ≡ 2 mod 6 forces even: no solution), or it is consistent and has a unique solution modulo the LCM of the moduli. This calculator detects non-coprime input and declines rather than guessing — solving that generalized case requires checking gcd-consistency first, a step worth doing deliberately.

Where is CRT used in real life?

Cryptography first: RSA's CRT optimization performs decryption and signing modulo each prime factor and recombines, roughly quadrupling speed — implemented in OpenSSL and every smart card. Beyond that: residue number systems in signal processing hardware, secret sharing schemes (via the polynomial cousin over finite fields), calendar/coincidence problems, error-correcting codes built on remainder representations, and the GPS-era trick of resolving phase ambiguities in satellite ranging, where multiple wavelengths' remainders pin down one distance — the Sunzi puzzle with lasers.

How many congruences can this calculator solve?

Three at a time (set the third modulus to 1 to solve just two). The method extends to any count by the same folding: solve the first two into a single congruence modulo their product, fold the next, repeat — the period multiplies at each step. For four or more congruences, run this calculator iteratively: combine any two, treat the result (x₀ mod product) as a new first congruence, and continue. Each fold is one screen of arithmetic.

Why does the solution repeat every 105 in the example?

Because adding the full product M = 3 × 5 × 7 = 105 adds a whole number of each modulus (105 is 35 threes, 21 fives, 15 sevens), leaving every remainder untouched. Any two solutions must differ by a common multiple of all moduli, and for coprime moduli the smallest such is the product — so solutions form a single arithmetic progression with period M. That periodicity is why "the answer" is really a residue class, and the smallest non-negative member is its canonical representative.

What is a modular inverse?

The number u with M·u ≡ 1 (mod m) — division's replacement in modular arithmetic, existing exactly when gcd(M, m) = 1 (the CRT's coprimality, again). The extended Euclidean algorithm produces it: for M = 3 mod 5, the inverse is 2, since 3 × 2 = 6 ≡ 1 (mod 5). CRT's construction is essentially solving for these inverses and assembling the solution from them; RSA key generation uses the same operation to build the private exponent from the public one.

Is this Chinese remainder theorem calculator free?

Yes — free, instant, no sign-up. Enter up to three remainder/modulus pairs for the smallest solution, the full solution family and a remainder-by-remainder verification.