Chinese Remainder Theorem Calculator

Solve systems of linear congruences

Enter a system of congruences and find the unique solution using the Chinese Remainder Theorem. This calculator supports multiple congruence equations with pairwise coprime moduli.

Congruence Equation 1

x ≡ 0 (mod 2)

Congruence Equation 2

x ≡ 0 (mod 3)
Example Congruence Systems

Click on any example to load it into the calculator

Basic System (2 equations)

basic

Simple system with small moduli to demonstrate the theorem

x ≡ 2 (mod 3)

x ≡ 3 (mod 5)

Intermediate System (3 equations)

intermediate

Three congruences with different remainder patterns

x ≡ 1 (mod 7)

x ≡ 4 (mod 9)

x ≡ 6 (mod 11)

Advanced System (4 equations)

advanced

Larger system demonstrating the theorem's power

x ≡ 3 (mod 5)

x ≡ 1 (mod 7)

x ≡ 6 (mod 11)

x ≡ 9 (mod 13)

Real-World Application

practical

Calendar and scheduling problem using CRT

x ≡ 0 (mod 7)

x ≡ 2 (mod 30)

x ≡ 15 (mod 365)

Other Titles
Understanding Chinese Remainder Theorem: A Comprehensive Guide
Master the fundamental theorem of number theory that solves systems of congruences with powerful applications in mathematics and computer science

What is the Chinese Remainder Theorem?

  • Historical origins and mathematical significance
  • Fundamental concepts of congruences and modular arithmetic
  • The theorem's statement and conditions for applicability
The Chinese Remainder Theorem (CRT) is one of the most elegant and powerful results in elementary number theory. Originally discovered by Chinese mathematician Sun Tzu around the 3rd century AD, this theorem provides a method for solving systems of simultaneous linear congruences with pairwise coprime moduli.
A congruence is a statement of the form x ≡ a (mod m), which means that x and a have the same remainder when divided by m. The Chinese Remainder Theorem tells us that if we have a system of such congruences with moduli that are pairwise coprime (their greatest common divisor is 1), then there exists a unique solution modulo the product of all moduli.
Theorem Statement:
Let m₁, m₂, ..., mₖ be pairwise coprime positive integers, and let a₁, a₂, ..., aₖ be any integers. Then the system of congruences:
x ≡ a₁ (mod m₁), x ≡ a₂ (mod m₂), ..., x ≡ aₖ (mod mₖ)
has a unique solution modulo M = m₁ × m₂ × ... × mₖ.
Key Requirements:
The moduli must be pairwise coprime, meaning gcd(mᵢ, mⱼ) = 1 for all i ≠ j. This condition is essential for the theorem to work and guarantees the existence and uniqueness of the solution.

Basic Understanding

  • Basic example: x ≡ 2 (mod 3) and x ≡ 3 (mod 5) has solution x ≡ 8 (mod 15)
  • The moduli 3 and 5 are coprime since gcd(3,5) = 1
  • Verification: 8 ≡ 2 (mod 3) ✓ and 8 ≡ 3 (mod 5) ✓

Step-by-Step Solution Method

  • The constructive proof algorithm for finding solutions
  • Computing partial products and modular inverses
  • Assembling the final solution using Bézout coefficients
The Chinese Remainder Theorem not only guarantees the existence of a solution but also provides a constructive method to find it. The algorithm involves several systematic steps that build up the solution piece by piece.
Step 1: Verify Coprimality
First, ensure all moduli are pairwise coprime by computing gcd(mᵢ, mⱼ) = 1 for all pairs i ≠ j. If any pair is not coprime, the theorem doesn't apply and the system may have no solution or infinitely many solutions.
Step 2: Compute the Total Modulus
Calculate M = m₁ × m₂ × ... × mₖ, the product of all moduli. The final solution will be unique modulo M.
Step 3: Calculate Partial Products
For each congruence i, compute Mᵢ = M / mᵢ. These are the partial products that will be used to construct the solution.
Step 4: Find Modular Inverses
For each i, find yᵢ such that Mᵢ × yᵢ ≡ 1 (mod mᵢ). This yᵢ is the modular inverse of Mᵢ modulo mᵢ, found using the Extended Euclidean Algorithm.
Step 5: Construct the Solution
The solution is given by: x ≡ (a₁M₁y₁ + a₂M₂y₂ + ... + aₖMₖyₖ) (mod M)

Algorithm Application

  • For x ≡ 2 (mod 3), x ≡ 3 (mod 5): M = 15, M₁ = 5, M₂ = 3
  • Find inverses: 5y₁ ≡ 1 (mod 3) → y₁ = 2, 3y₂ ≡ 1 (mod 5) → y₂ = 2
  • Solution: x ≡ 2×5×2 + 3×3×2 ≡ 20 + 18 ≡ 38 ≡ 8 (mod 15)

Real-World Applications and Use Cases

  • Cryptography and RSA encryption applications
  • Computer science algorithms and data structures
  • Calendar calculations and astronomical problems
The Chinese Remainder Theorem has numerous practical applications across mathematics, computer science, and engineering. Its ability to break down complex modular problems into simpler, independent subproblems makes it invaluable in many computational contexts.
Cryptography and Security:
In RSA encryption, the CRT is used to speed up decryption operations. Instead of computing large exponentiations directly, the computation is split into smaller problems modulo the prime factors of the RSA modulus, then recombined using CRT. This can provide a speedup of up to 4 times.
Computer Algorithms:
The theorem is used in parallel computing for distributing large integer computations across multiple processors. It's also fundamental in designing efficient algorithms for polynomial arithmetic and fast Fourier transforms.
Calendar and Time Calculations:
CRT helps solve problems involving multiple periodic cycles, such as finding when certain calendar events coincide. For example, determining when a particular day of the week falls on a specific date in multiple calendar systems.
Error Correction Codes:
In coding theory, CRT is used to construct error-correcting codes that can detect and correct errors in data transmission by representing information redundantly across multiple modular channels.
Mathematical Problem Solving:
The theorem provides elegant solutions to many classical number theory problems, including finding patterns in sequences, solving Diophantine equations, and analyzing periodic phenomena.

Practical Applications

  • RSA decryption: Computing m ≡ c^d (mod n) using CRT with n = p×q
  • Calendar problem: Finding dates that are Monday (mod 7), 1st of month (mod 30), and leap year (mod 4)
  • Hash table design: Using CRT for constructing perfect hash functions
  • Signal processing: Reconstructing signals from multiple sampling rates

Common Misconceptions and Troubleshooting

  • Understanding when the theorem applies and when it doesn't
  • Dealing with non-coprime moduli and alternative approaches
  • Avoiding computational errors in the solution process
While the Chinese Remainder Theorem is powerful, it's important to understand its limitations and common pitfalls that can lead to incorrect applications or computational errors.
Misconception 1: The Theorem Always Applies
Incorrect: The CRT can be used for any system of congruences regardless of the moduli.
Correct: The moduli must be pairwise coprime. If gcd(mᵢ, mⱼ) > 1 for any pair, the standard CRT doesn't apply. In such cases, the system may have no solution or require different techniques.
Misconception 2: Solutions Are Always Unique
Incorrect: There's always exactly one solution to a congruence system.
Correct: The solution is unique only modulo M = m₁ × m₂ × ... × mₖ. There are infinitely many solutions of the form x + kM for integer k.
Misconception 3: Modular Inverse Always Exists
Incorrect: Every number is invertible modulo any modulus.
Correct: A number a has an inverse modulo m only if gcd(a, m) = 1. This is automatically satisfied in CRT due to the coprimality requirement.
Common Computational Errors:
  • Forgetting to reduce intermediate results modulo the appropriate modulus
  • Confusing the direction of modular inverse computation
  • Not properly handling negative remainders in some programming languages
  • Arithmetic overflow when dealing with large moduli

Error Prevention

  • Non-coprime case: x ≡ 1 (mod 6), x ≡ 3 (mod 9) has no solution since gcd(6,9) = 3
  • Multiple solutions: x ≡ 8 (mod 15) represents {..., -7, 8, 23, 38, ...}
  • Inverse error: 2 has no inverse mod 6 since gcd(2,6) = 2 ≠ 1
  • Overflow prevention: Use modular arithmetic throughout computation

Mathematical Theory and Advanced Topics

  • Theoretical foundations and proof techniques
  • Generalizations to rings and abstract algebra
  • Connections to other areas of mathematics
The Chinese Remainder Theorem has deep theoretical foundations that connect to many areas of abstract algebra, number theory, and computational mathematics. Understanding these connections provides insight into why the theorem works and how it can be generalized.
Ring-Theoretic Formulation:
In abstract algebra, the CRT states that if R is a ring and I₁, I₂, ..., Iₖ are pairwise coprime ideals, then R/(I₁ ∩ I₂ ∩ ... ∩ Iₖ) ≅ R/I₁ × R/I₂ × ... × R/Iₖ. For integers, this becomes ℤ/nℤ ≅ ℤ/m₁ℤ × ℤ/m₂ℤ × ... × ℤ/mₖℤ when n = m₁m₂...mₖ.
Constructive vs. Existence Proofs:
There are several ways to prove the CRT. The constructive proof provides the algorithm we use for computation, while existence proofs using group theory or ring isomorphisms give different insights into why the theorem holds.
Computational Complexity:
The CRT algorithm runs in O(k log²(M)) time where k is the number of congruences and M is the product of moduli. The bottleneck is usually computing modular inverses using the Extended Euclidean Algorithm.
Generalizations and Extensions:
The theorem extends to polynomial rings, matrix rings, and other algebraic structures. In coding theory, it's generalized to Reed-Solomon codes. In algebraic geometry, it relates to sheaf cohomology and scheme theory.
Connection to Other Theorems:
CRT is closely related to the fundamental theorem of arithmetic, Bézout's identity, and the structure theorem for finitely generated abelian groups. It also connects to the Sunzi's theorem in ancient Chinese mathematics.

Advanced Mathematical Examples

  • Ring isomorphism: ℤ/15ℤ ≅ ℤ/3ℤ × ℤ/5ℤ demonstrates the algebraic structure
  • Polynomial CRT: Solving f(x) ≡ gᵢ(x) (mod pᵢ(x)) for coprime polynomials pᵢ(x)
  • Matrix application: Block diagonal decomposition using CRT principles
  • Complexity example: For 4 congruences with 100-bit moduli, expect ~400 bit operations