Chinese Remainder Theorem Solver

Solve systems of congruences using the Chinese Remainder Theorem (CRT). Calculate the unique solution modulo the product of moduli.

Chinese Remainder Theorem (CRT): If moduli m₁, m₂, ..., mₙ are pairwise coprime, then the system of congruences x ≡ aᵢ (mod mᵢ) has a unique solution modulo M = m₁ × m₂ × ... × mₙ.

1
Congruence 1
The remainder when x is divided by m
The divisor (must be positive)
x ≡ 2 (mod 3)
2
Congruence 2
The remainder when x is divided by m
The divisor (must be positive)
x ≡ 3 (mod 5)
Example Systems:
Standard Example
Three Congruences
Sun Zi's Problem
Pairwise Coprime
Non-coprime (Invalid)
Non-coprime but Solvable
Large Numbers
Single Congruence

Calculating...

Understanding the Chinese Remainder Theorem

The Chinese Remainder Theorem (CRT) is a theorem in number theory that provides a unique solution to a system of simultaneous congruences with pairwise coprime moduli. It has applications in cryptography, computer science, and coding theory.

Mathematical Statement:

Given pairwise coprime positive integers m₁, m₂, ..., mₙ and arbitrary integers a₁, a₂, ..., aₙ, 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ₙ.

Solution Algorithm

1

Compute M: Calculate the product of all moduli: M = m₁ × m₂ × ... × mₙ

2

Compute Mᵢ: For each modulus mᵢ, compute Mᵢ = M / mᵢ

3

Find inverses: For each i, find yᵢ such that Mᵢ × yᵢ ≡ 1 (mod mᵢ) using the extended Euclidean algorithm

4

Compute solution: x = Σ(aᵢ × Mᵢ × yᵢ) mod M

Extended Euclidean Algorithm

The extended Euclidean algorithm finds integers x and y such that ax + by = gcd(a, b). It's used to find modular inverses in the CRT solution.

Step Quotient q Remainder r x y
0 17 1 0
1 5 0 1
2 3 2 1 -3
3 2 1 -2 7
4 2 0 5 -17

Example: Finding the inverse of 5 modulo 17 gives 7, since 5×7 = 35 ≡ 1 (mod 17)

Applications of CRT

  • Cryptography: RSA algorithm, secret sharing schemes
  • Computer Science: Fast integer arithmetic, error-correcting codes
  • Number Theory: Solving Diophantine equations, modular arithmetic
  • Engineering: Signal processing, calendar calculations
  • Mathematics: Ring isomorphisms, interpolation

Calculator Features:

  • Handles any number of congruences (add or remove as needed)
  • Checks pairwise coprimality of moduli
  • Shows step-by-step solution using the CRT algorithm
  • Uses extended Euclidean algorithm to find modular inverses
  • Verifies the solution against all congruences
  • Provides the general solution formula

Frequently Asked Questions

Pairwise coprime means that every pair of moduli has a greatest common divisor of 1. For example, {3, 5, 7} are pairwise coprime because gcd(3,5)=1, gcd(3,7)=1, and gcd(5,7)=1. However, {2, 4, 5} are not pairwise coprime because gcd(2,4)=2 ≠ 1.

The standard Chinese Remainder Theorem requires pairwise coprime moduli. For non-coprime moduli, a solution may still exist if all congruences are consistent, but it's not guaranteed. In such cases, you can often break down the system into one with coprime moduli by combining moduli with common factors.

The Chinese Remainder Theorem establishes a ring isomorphism between ℤ/Mℤ (integers modulo M) and the direct product of rings ℤ/m₁ℤ × ℤ/m₂ℤ × ... × ℤ/mₙℤ when the mᵢ are pairwise coprime. This is why we can solve systems of congruences by working component-wise.

The CRT algorithm has time complexity O(n² log M) for n congruences, where M is the product of all moduli. The most computationally intensive part is finding modular inverses using the extended Euclidean algorithm, which has complexity O(log min(a,b)) for finding the inverse of a modulo b.

In RSA, CRT is used to speed up decryption. Instead of computing m = cᵈ mod n directly (which is slow for large n), we compute m₁ = cᵈ mod p and m₂ = cᵈ mod q, where n = p×q. Then we use CRT to combine m₁ and m₂ to get m mod n. This is about 4 times faster than direct computation.