How to Use Chinese Remainder Theorem Calculator
The Chinese Remainder Theorem Calculator solves systems of simultaneous congruences. Each row represents one equation of the form x ≡ aᵢ (mod mᵢ). Fill in the rows and the Chinese Remainder Theorem Calculator computes the minimum non-negative solution and the general form immediately.
- Enter remainders and moduli — for each row, type the remainder aᵢ and the modulus mᵢ. Add more rows with the “Add Congruence” button for systems with more than three equations.
- Check pairwise coprimality — the Chinese Remainder Theorem Calculator automatically verifies that all moduli are pairwise coprime. If they are not, an error message explains why.
- Read the solution — the result panel shows the minimum non-negative solution x, the general solution form x ≡ r (mod M), the total modulus M, and a step-by-step table with Mᵢ, yᵢ, and aᵢMᵢyᵢ values.
You can add up to any number of congruences. Remove a row by clicking the ✕ button next to it.
Formula & Theory - Chinese Remainder Theorem Calculator
The Chinese Remainder Theorem Calculator implements the standard CRT construction:
Given: x ≡ a₁ (mod m₁), x ≡ a₂ (mod m₂), ..., x ≡ aₙ (mod mₙ)
Require: m₁, m₂, ..., mₙ pairwise coprime
M = m₁ × m₂ × ... × mₙ
Mᵢ = M / mᵢ
yᵢ = modular inverse of Mᵢ with respect to mᵢ (Mᵢ · yᵢ ≡ 1 mod mᵢ)
x = (Σ aᵢ · Mᵢ · yᵢ) mod M| Symbol | Meaning |
|---|---|
| M | Product of all moduli |
| Mᵢ | M divided by the i-th modulus |
| yᵢ | Modular inverse of Mᵢ modulo mᵢ |
| x | Minimum non-negative solution |
The theorem guarantees a unique solution modulo M when all moduli are pairwise coprime. The Chinese Remainder Theorem Calculator uses the Extended Euclidean Algorithm to compute each modular inverse, ensuring correctness for arbitrarily large moduli (within JavaScript’s safe integer range).
Assumptions and Limits
- All moduli must be positive integers greater than 1.
- Remainders can be any integer; negative remainders are automatically normalized.
- The CRT as implemented requires pairwise coprime moduli. Generalized CRT for non-coprime moduli is outside the scope of this calculator.
- Large moduli may exceed JavaScript’s safe integer range (2⁵³ − 1). For very large inputs, consider specialized big-integer tools.
Use Cases for Chinese Remainder Theorem Calculator
The Chinese Remainder Theorem Calculator is useful in both academic and applied settings. Common scenarios include:
- Number theory homework — quickly solve CRT problems assigned in discrete mathematics or abstract algebra courses.
- Cryptography foundations — CRT is a core technique in RSA optimization (Chinese Remainder Theorem form of RSA), Diffie-Hellman key exchange, and other public-key algorithms.
- Algorithm competitions — competitive programming problems frequently involve simultaneous congruences; the Chinese Remainder Theorem Calculator lets you verify answers before submitting.
- Clock arithmetic puzzles — classic puzzles such as “a number leaves remainder 2 when divided by 3, remainder 3 when divided by 5, …” are solved instantly.
The step-by-step table makes the Chinese Remainder Theorem Calculator especially useful for learning the algorithm, not just getting answers.