The calculator does not require the moduli to be pairwise coprime. If two moduli share a non-trivial gcd, it checks whether the corresponding remainders agree modulo that gcd. If they do, the congruences can still be merged; otherwise, the system has no solution and the conflicting pair is reported explicitly.
Chinese Remainder Theorem Calculator
Chinese remainder theorem calculator. Solve systems of congruences x ≡ ai (mod mi), detect incompatibilities, and see step-by-step CRT construction and the combined modulus.
CRT system solver
Between 2 and 8 rows. Empty rows are ignored.
Example: x ≡ 2 (mod 3), x ≡ 3 (mod 5), x ≡ 2 (mod 7).
Notes:
- Moduli mᵢ must be positive integers.
- The solver uses arbitrary-precision integers (BigInt) for robustness.
System status
Awaiting calculation
Least nonnegative solution x₀
—
Combined modulus M
—
Notes
Fill the table and click Calculate.
Solution details will appear here after you click Calculate.
How to use this calculator
Set the number of congruences to solve (between 2 and 8), then enter each remainder aᵢ and a positive modulus mᵢ. Leave any unused rows completely blank—only filled rows are processed.
Click Calculate to run the solver. The tool normalizes remainders into the canonical range, merges congruences sequentially, and reports either a least nonnegative solution x₀ plus the final modulus M or the conflicting congruences when no solution exists.
Methodology
We implement the generalized Chinese remainder theorem. The calculator tracks a running congruence x ≡ a (mod n) and merges each new equation x ≡ b (mod m) by enforcing gcd-based compatibility, then computing a modular inverse via the extended Euclidean algorithm. The combined modulus n expands to lcm(n, m) at every successful merge.
- Each merge verifies that the remainders agree modulo g = gcd(n, m). If they do not, the system is inconsistent.
- The inverse of n/g modulo m/g produces the increment needed to align the combined solution.
- Once all rows are merged, the solution set is x ≡ x₀ (mod M) with M being the least common multiple of the provided moduli.
Figures are exact big-integer calculations. The solver highlights compatibility issues explicitly so you can correct individual congruences.
All solutions follow x = x₀ + k·M for integer k.
All solutions follow x = x₀ + k·M for integer k.
Full original guide (expanded)
CRT system solver
Generalized Chinese remainder theoremSolve systems of congruences of the form x ≡ aᵢ (mod mᵢ). The tool checks consistency, handles non-coprime moduli, and shows a least nonnegative solution if one exists.
Enter your congruences and click Calculate. The solver uses the extended Euclidean algorithm, detects incompatibilities, and reports the solution modulo the combined modulus.
Press Calculate to solve, or Reset to start over.
Backend: extended Euclidean algorithm and iterative CRT merging.
Solution, combined modulus, and step-by-step CRT construction will appear here after you click Calculate.
Chinese remainder theorem – definition and intuition
The Chinese remainder theorem (CRT) describes when a system of congruences x ≡ a₁ (mod m₁), x ≡ a₂ (mod m₂), … has a solution and how to describe all solutions. If the congruences are mutually compatible, there is a unique solution modulo the least common multiple of the moduli.
Classical CRT with pairwise coprime moduli
In the classical setting, the moduli m₁,…,mₖ are pairwise coprime (gcd(mᵢ, mⱼ) = 1 for i ≠ j). Let M = m₁ m₂ ··· mₖ and define Mᵢ = M / mᵢ along with the modular inverse Nᵢ ≡ Mᵢ⁻¹ (mod mᵢ). Then an explicit solution is given by x₀ ≡ Σᵢ aᵢ Mᵢ Nᵢ (mod M), and all solutions follow x = x₀ + tM for t ∈ ℤ.
Generalized CRT with non-coprime moduli
When moduli are not pairwise coprime, two congruences x ≡ a₁ (mod m₁) and x ≡ a₂ (mod m₂) are compatible if and only if a₁ ≡ a₂ (mod gcd(m₁, m₂)). In this case the merged modulus becomes lcm(m₁, m₂). If that compatibility condition fails, the calculator reports the conflicting pair instead of producing a false solution.
Algorithm used by the calculator
Let x ≡ a (mod n) denote the running combined congruence before merging x ≡ b (mod m). The steps are:
- Compute g = gcd(n, m).
- If a ≢ b (mod g), the system is inconsistent and no solution exists.
- Otherwise set n₁ = n/g, m₁ = m/g, and r = (b − a)/g.
- Find the modular inverse of n₁ modulo m₁ using the extended Euclidean algorithm.
- Compute t ≡ r · n₁⁻¹ (mod m₁) and update x = a + n·t, N = n·m₁.
After processing every congruence, a single congruence x ≡ x₀ (mod N) encodes all solutions, where N = lcm of the original moduli.
Applications: from calendars to cryptography
The Chinese remainder theorem appears in many contexts:
- Calendar calculations and periodic scheduling,
- Coding theory and cryptographic schemes such as RSA,
- Modular arithmetic with large integers via residue systems,
- Programming contests and algorithmic number theory.
In each case, CRT allows a large modular problem to be broken into smaller, independent pieces that are recombined consistently.