Chinese Remainder Calculator - CRT Constructive Solver

A Chinese Remainder Calculator is a number-theory tool that solves a system of simultaneous congruences such as x ≡ 2 (mod 3) and x ≡ 3 (mod 5), returning the unique integer x in 0 ≤ x < N that satisfies every row. The Chinese Remainder Theorem ensures a solution when the moduli are pairwise coprime, and the constructive formula combines the residues aᵢ, the partial products Nᵢ, and modular inverses to deliver the answer in one pass. Use this tool to verify textbook exercises, decode large integers from their residues, or check the modular arithmetic behind RSA, secret sharing, and other cryptography constructions.

• • Homework and Exam Verification: Check CRT systems from a discrete math or number theory course against a known answer without re-deriving the formula by hand.
• • RSA and Cryptography Work: Reconstruct a large integer from its residues modulo several primes, the idea behind RSA-CRT, the private-key optimization that splits signing and decryption into two coprime congruences.
• • Lunar and Calendar Puzzles: Solve classic Sun Zi problems like a number that leaves a given remainder when divided by 3, 5, and 7, the textbook motivation behind the theorem.
• • Decoding Chinese Remainder Inputs: Convert a CRT-encoded integer back to its base-10 form when the residues are stored modulo several coprime factors, useful in computer algebra.

The Chinese Remainder Theorem is one of the cleanest constructive results in elementary number theory, and the same proof that powers the theorem also gives a usable algorithm. To brush up on the underlying modular arithmetic before applying the theorem, the Modulo Calculator computes remainders, modular inverses, and modular exponentiation with steps.

The calculator reads each line as one congruence x ≡ aᵢ (mod nᵢ), validates the pairwise coprime assumption, and then assembles the constructive CRT formula with a single pass over the equations.

• aᵢ: The residue on row i, the remainder that x must leave when divided by nᵢ.
• nᵢ: The modulus on row i. Must be ≥ 2 and pairwise coprime with every other nⱼ.
• N: The product of all moduli. The solution x is unique modulo N.
• Nᵢ: The partial product N / nᵢ. It scales the i-th residue and zeroes out every other row.
• Mᵢ: The modular inverse of Nᵢ modulo nᵢ, so that Nᵢ·Mᵢ ≡ 1 (mod nᵢ).

The algorithm has three phases. First the calculator validates the input, rejecting negative residues, moduli below 2, and any pair of moduli whose greatest common divisor exceeds 1. Second it computes the partial products Nᵢ and the modular inverses Mᵢ using the extended Euclidean algorithm, the same routine that powers the Modulo Calculator. Finally it sums aᵢ·Nᵢ·Mᵢ over every row and reduces the result modulo N to obtain the canonical x.

When the input is a single congruence the theorem reduces to a trivial identity, so the calculator returns the residue with N equal to that modulus and the family a + n·k. Two and three equation systems are the most common, but the implementation scales further.

According to Wikipedia - Chinese remainder theorem, the theorem states that for a system x ≡ aᵢ (mod nᵢ) with pairwise coprime moduli there is a unique solution modulo N = ∏ nᵢ given by x = Σ aᵢ·Nᵢ·Mᵢ (mod N) where Nᵢ = N/nᵢ and Mᵢ is the modular inverse of Nᵢ modulo nᵢ.

The same extended Euclidean algorithm that produces the modular inverses Mᵢ also powers the n! mod p and double-factorial problems the Factorial Calculator handles, so the constructive result feeds straight into it.

These four concepts sit behind every CRT calculation, so it is worth keeping them straight before reading the result.

The constructive proof does double duty as an algorithm, which is why CRT shows up inside RSA private-key operations like signing and decryption, secret sharing, and many database sharding schemes. Pairwise coprime moduli are easiest to ensure when each nᵢ is itself prime, and the Prime Number Checker confirms primality in one step.

The constructive formula has an even older setting: Sun Zi's Mathematical Classic in Nine Chapters worked a problem with moduli 3, 5, and 7 in the third century CE. The garbled-mail story attached to the theorem describes using a CRT-like construction to recover a clear message from interleaved garbled copies sent on different routes.

Enter one congruence per line in the text box, then read the canonical x, the combined modulus N, and the constructive steps in the result panel.

1. 1 Write the Congruences: Type one row per congruence in the form 'a n'. Use a space, comma, or tab between the residue and the modulus. Add as many rows as your system needs.
2. 2 Confirm the Moduli Are Pairwise Coprime: Make sure that any two moduli share no common factor other than 1. The calculator will surface a clear error if it spots a conflict.
3. 3 Run the Calculation: The result panel updates automatically as you type. The primary result is the canonical x in the range 0 ≤ x < N, with the combined modulus N underneath.
4. 4 Inspect the Constructive Steps: Open the constructive steps card to see each Nᵢ, the modular inverse Mᵢ, and the per-row contribution aᵢ·Nᵢ·Mᵢ. This is enough to verify the answer by hand.
5. 5 Reuse the Full Solution Family: Use the family x + k·N whenever you need the next valid integer. The modulo operation behind this family is the same one exposed by the Modulo Calculator.

If you enter '1 2\n2 3\n3 5\n5 7' the calculator returns x = 173 with N = 210, so the full solution set is 173 + 210k for any integer k. Spot-check: 173 mod 2 = 1, 173 mod 3 = 2, 173 mod 5 = 3, 173 mod 7 = 5.

The pairwise coprime check uses the same GCD simplification the Fraction Calculator applies to reduce a fraction to lowest terms, so reducing aᵢ/nᵢ as an ordinary fraction is a quick preview of the coprime check.

This Chinese Remainder Calculator replaces a hand-rolled constructive proof with a tool that delivers the same answer in one pass and prints every intermediate value a student needs.

• • Constructive Formula Built In: The calculator applies Σ aᵢ·Nᵢ·Mᵢ directly, so you do not have to derive the partial-product recipe by hand.
• • Pairwise Coprime Validation: The input is checked for shared factors and a clear error is shown, which prevents the silent failure that catches many students.
• • Auditable Per-Row Steps: Each row's Nᵢ, Mᵢ, and contribution are printed, so the final x is fully traceable.
• • Scales to Any Number of Equations: Two-equation systems, the three-row Sun Zi problem, and longer inputs use the same calculator.
• • Full Solution Family Output: Beyond the canonical x, the tool reports the family x + k·N, which is the form you usually need for subsequent modular arithmetic.

Because the result is the unique solution in 0 ≤ x < N, the calculator is a one-stop check for any CRT exercise. The constructive steps and family output also feed into the modulo arithmetic behind the Modulo Calculator, so the two tools pair well inside a number-theory workflow.

The constructive formula is a quotient-and-remainder operation across the rows, and the Polynomial Division Calculator applies the same divide-and-reduce pattern to polynomials with explicit quotient and remainder steps.

Three input choices and one mathematical precondition control every CRT answer, and they are worth understanding before you scale up.

• • The calculator requires the moduli to be pairwise coprime. Systems where two congruences share a common factor can be inconsistent or have infinitely many solutions, and those cases are out of scope.
• • The result is the smallest nonnegative integer x, not a family of residues. The full family x + k·N is reported separately so the user can pick the form they need.
• • Negative residues are rejected. If your source problem gives a negative remainder, add nᵢ to the residue first.

If a system is inconsistent, the calculator does not try to find the largest consistent subsystem. The general case reduces to checking each pair of congruences for shared factors and is handled outside the constructive proof. For systems with non-coprime moduli, a separate extended CRT routine is required.

When the constructive proof breaks down because the moduli share a factor, lifting the problem into a richer ring can sometimes recover a solution, but those reformulations sit outside the scope of this calculator and are best worked by hand.

As published by Wolfram MathWorld - Chinese Remainder Theorem, the Chinese remainder theorem constructs a solution by computing partial products Nᵢ and modular inverses Mᵢ, then summing aᵢ·Nᵢ·Mᵢ to obtain x in the range 0 ≤ x < N.