About

The Chinese Remainder Theorem (CRT) guarantees a unique solution modulo M = m₁ ⋅ m₂ ⋅ … ⋅ m_k for a system of simultaneous congruences x ≡ a_i (mod m_i), provided all moduli are pairwise coprime. Failing the coprimality condition means no solution may exist, or the solution is not unique. Manual computation breaks down rapidly as the product M grows, requiring modular inverses via the Extended Euclidean Algorithm at each step. An arithmetic error in any single inverse propagates through the entire sum and produces a wrong answer silently.

This calculator uses arbitrary-precision integer arithmetic (BigInt) to handle moduli of any practical size without overflow. It validates pairwise coprimality before attempting construction and reports exactly which pair of moduli share a common factor. The step-by-step output exposes every intermediate value (M_i, y_i, partial products) so you can verify or use them in coursework. Note: CRT applies only when all moduli are pairwise coprime. For non-coprime systems, the generalized CRT requires compatibility conditions on remainders that this tool does not cover.

Formulas

Given k simultaneous congruences:

x ≡ a₁ (mod m₁), x ≡ a₂ (mod m₂), … x ≡ a_k (mod m_k)

where all m_i are pairwise coprime (gcd(m_i, m_j) = 1 for i ≠ j), compute the combined modulus:

M = k∏i=1 m_i

For each i, compute the partial product and its modular inverse:

M_i = Mm_i, y_i = M_i⁻¹ (mod m_i)

The modular inverse y_i is found via the Extended Euclidean Algorithm, which solves M_i ⋅ y_i + m_i ⋅ t = 1. The unique solution modulo M is:

x ≡ k∑i=1 a_i ⋅ M_i ⋅ y_i (mod M)

Where a_i = remainder for congruence i, m_i = modulus for congruence i, M = product of all moduli, M_i = partial product excluding m_i, y_i = modular inverse of M_i modulo m_i, x = unique solution in [0, M − 1].

Reference Data

System Size	Moduli Example	Product M	Solution x	Domain
2	3, 5	15	x ≡ 2 (mod 3), x ≡ 3 (mod 5) → 8	Textbook intro
3	3, 5, 7	105	x ≡ 2, 3, 2 → 23	Classic puzzle
2	7, 11	77	x ≡ 3, 6 → 17	Cryptography basics
3	4, 9, 25	900	x ≡ 1, 2, 3 → 353	Prime power moduli
4	2, 3, 5, 7	210	x ≡ 1, 2, 3, 4 → 53	Scheduling / cycles
2	11, 13	143	x ≡ 7, 9 → 139	RSA sub-step
3	5, 7, 11	385	x ≡ 0, 0, 0 → 0	Trivial case
2	100, 37	3700	x ≡ 55, 22 → 355	Competition math
5	2, 3, 5, 7, 11	2310	x ≡ 1 for all → 1	All-ones identity
3	8, 27, 125	27000	x ≡ 5, 10, 15 → 6265	Prime power cubes
2	17, 19	323	x ≡ 10, 15 → 300	Number theory HW
4	3, 5, 7, 11	1155	x ≡ 2, 4, 6, 10 → 494	Extended system
2	1000000007, 998244353	≈ 10¹⁸	Requires BigInt	Competitive programming

Frequently Asked Questions

The standard CRT requires gcd(m_i, m_j) = 1 for every pair. If two moduli share a factor, the system may have no solution or requires the generalized CRT, which adds compatibility conditions: a_i ≡ a_j (mod gcd(m_i, m_j)). This calculator rejects non-coprime inputs and reports exactly which pair fails.

Yes. All internal arithmetic uses JavaScript BigInt, which supports integers of arbitrary size limited only by available memory. Moduli in the range of 10¹⁸ or beyond are handled without overflow. Competitive programming primes like 1000000007 and 998244353 work correctly.

The inverse is computed via the Extended Euclidean Algorithm. Given M_i and m_i, it finds y_i such that M_i ⋅ y_i ≡ 1 (mod m_i). The inverse exists if and only if gcd(M_i, m_i) = 1, which is guaranteed when the moduli are pairwise coprime. If coprimality is violated, the algorithm correctly detects the failure.

The CRT guarantees a unique solution modulo M = m₁ ⋅ m₂ ⋅ … ⋅ m_k. The calculator returns the smallest non-negative representative x ∈ [0, M − 1]. The general solution is x + n ⋅ M for any integer n.

The Extended Euclidean Algorithm naturally produces Bézout coefficients that can be negative. For instance, solving 35 ⋅ y ≡ 1 (mod 3) may yield y = −1. The calculator normalizes the final result to [0, M − 1] but shows raw intermediates for educational transparency.

There is no hard-coded limit. Practically, the pairwise coprimality check is O(k²) and the product M grows exponentially with k. Systems of 20 - 50 congruences with moderate moduli compute instantly. Extremely large systems with enormous moduli may cause browser memory pressure due to BigInt size.