Chinese Remainder Theorem Calculator

Solve x ≡ a₁ (mod m₁), x ≡ a₂ (mod m₂), ... with step-by-step Extended Euclidean Algorithm

Quick Examples

Remainder (aᵢ)

Modulus (mᵢ)

Congruence

What is the Chinese Remainder Theorem (CRT)?

The Chinese Remainder Theorem is one of the oldest results in number theory. It states that if m₁, m₂, ..., mₙ are pairwise coprime positive integers (every pair has GCD = 1), then the system of simultaneous congruences:

x ≡ a₁ (mod m₁)
x ≡ a₂ (mod m₂)
⋮
x ≡ aₙ (mod mₙ)

has a unique solution modulo M = m₁ × m₂ × ... × mₙ. This means there is exactly one integer x in the range [0, M) that satisfies all congruences simultaneously, and all other solutions are of the form x₀ + kM for integer k.

The theorem originates from the Sunzi Suanjing (3rd–5th century AD China), which posed the classic problem: "Find a number that, when divided by 3, leaves a remainder of 2; when divided by 5, leaves 3; and when divided by 7, leaves 2." The answer is x = 23.

CRT Formula and Algorithm

The constructive proof of CRT gives an explicit formula for the solution:

M = m₁ × m₂ × ... × mₙ
Mᵢ = M / mᵢ (product of all moduli except mᵢ)
yᵢ ≡ Mᵢ⁻¹ (mod mᵢ) (modular inverse of Mᵢ)
x = (a₁·M₁·y₁ + a₂·M₂·y₂ + ... + aₙ·Mₙ·yₙ) mod M

The key insight is that each term aᵢ·Mᵢ·yᵢ ≡ aᵢ (mod mᵢ) and ≡ 0 (mod mⱼ) for j ≠ i, because Mᵢ is divisible by every mⱼ except mᵢ. This makes the terms "orthogonal" — each one handles exactly one congruence without disturbing the others.

Worked Example — Sunzi's Problem

Solve: x ≡ 2 (mod 3), x ≡ 3 (mod 5), x ≡ 2 (mod 7)

Step 1: M = 3 × 5 × 7 = 105

Step 2: Compute Mᵢ values
  M₁ = 105/3 = 35
  M₂ = 105/5 = 21
  M₃ = 105/7 = 15

Step 3: Find modular inverses yᵢ = Mᵢ⁻¹ (mod mᵢ)
  y₁ = 35⁻¹ mod 3: 35 ≡ 2 (mod 3), 2×2=4≡1 (mod 3) → y₁ = 2
  y₂ = 21⁻¹ mod 5: 21 ≡ 1 (mod 5), 1×1=1 (mod 5) → y₂ = 1
  y₃ = 15⁻¹ mod 7: 15 ≡ 1 (mod 7), 1×1=1 (mod 7) → y₃ = 1

Step 4: Combine
  x = (2×35×2) + (3×21×1) + (2×15×1) mod 105
  x = 140 + 63 + 30 = 233 mod 105
  x = 23 ✓

Verify: 23 mod 3 = 2 ✓, 23 mod 5 = 3 ✓, 23 mod 7 = 2 ✓. General solution: x = 23 + 105k for any integer k.

Extended Euclidean Algorithm

The modular inverse yᵢ = Mᵢ⁻¹ (mod mᵢ) is found using the Extended Euclidean Algorithm, which computes integers x and y satisfying Bezout's identity: a·x + b·y = GCD(a, b). When GCD(a, b) = 1, x (reduced mod b) is the modular inverse of a.

extGCD(a, b):
  if b = 0: return (a, 1, 0)
  (g, x₁, y₁) = extGCD(b, a mod b)
  return (g, y₁, x₁ - ⌊a/b⌋·y₁)

Example: inverse of 35 mod 3
  extGCD(2, 3): → (1, -1, 1) because 2×(-1) + 3×1 = 1
  (-1 mod 3 + 3) mod 3 = 2 → inverse = 2

The algorithm runs in O(log(min(a,b))) time — much faster than trial and error, especially for large moduli used in cryptography.

Conditions for CRT

Pairwise coprime moduli: GCD(mᵢ, mⱼ) = 1 for every i ≠ j. Without this, the theorem does not guarantee a unique solution.
Remainder range: Technically, aᵢ can be any integer, but the canonical form uses 0 ≤ aᵢ < mᵢ. Values outside this range can be reduced: use aᵢ mod mᵢ.
Positive moduli ≥ 2: Each mᵢ must be a positive integer at least 2 for the congruence to be meaningful.
Minimum 2 equations: A single congruence trivially has infinitely many solutions; CRT is meaningful for systems of 2 or more.

Applications of CRT

RSA Cryptography: CRT speeds up RSA decryption by a factor of ~4 by splitting the computation into two smaller modular exponentiations using the prime factors p and q of the RSA modulus.
Astronomy and Calendar Cycles: Finding when multiple periodic events (lunar month, solar year, specific celestial alignments) coincide uses CRT-style reasoning. The ancient Chinese Metonic cycle is a classic example.
Error-Correcting Codes: Redundant residue number systems (RNS) use CRT to reconstruct original values from partial (potentially erroneous) modular residues, enabling fault tolerance.
Computer Arithmetic: Residue Number Systems represent large integers as tuples of remainders modulo small pairwise coprime bases. Arithmetic on these tuples is embarrassingly parallel, and CRT reconstructs the final result.
Hash Functions and Secret Sharing: Shamir's Secret Sharing scheme uses polynomial interpolation over finite fields, closely related to CRT ideas for distributing a secret among multiple parties.

Frequently Asked Questions

What is the Chinese Remainder Theorem?

The Chinese Remainder Theorem (CRT) is a foundational result in number theory. It states that if m₁, m₂, ..., mₙ are pairwise coprime positive integers, then the system x ≡ a₁ (mod m₁), ..., x ≡ aₙ (mod mₙ) has a unique solution modulo M = m₁ × m₂ × ... × mₙ. The theorem dates to the Sunzi Suanjing (3rd–5th century AD) and is used today in cryptography, computer science, and calendar arithmetic.

What are pairwise coprime moduli?

Two integers are coprime if their GCD is 1 — they share no common prime factor. A set {m₁, m₂, ..., mₙ} is pairwise coprime if every pair (mᵢ, mⱼ) has GCD = 1. For example, {3, 5, 7} are pairwise coprime (all prime and distinct), while {4, 6} are not coprime because GCD(4, 6) = 2. Prime numbers are always pairwise coprime with each other.

How do I find a modular inverse?

The modular inverse of a modulo m is a number y such that a·y ≡ 1 (mod m). It exists only when GCD(a, m) = 1. The most efficient method is the Extended Euclidean Algorithm, which finds integers x, y satisfying a·x + m·y = GCD(a, m). For small values, you can also use brute force: find the y in {1, 2, ..., m−1} such that (a × y) mod m = 1.

What does the solution x₀ + kM mean?

CRT guarantees a unique solution in [0, M). That is x₀. Since the system repeats with period M, all integers of the form x₀ + kM (for any integer k ∈ ℤ) also satisfy the system. So x₀ + M, x₀ + 2M, x₀ − M, and so on are all valid solutions. x₀ is the canonical (smallest non-negative) representative.

Can CRT be used when moduli are not coprime?

The classical CRT requires pairwise coprime moduli. When moduli are not coprime, a solution may or may not exist. For the pair x ≡ a (mod m) and x ≡ b (mod n), a solution exists if and only if GCD(m, n) divides (b − a). If it exists, the solution is unique modulo LCM(m, n) rather than m×n. This generalization is sometimes called the "generalized CRT."

What is the Extended Euclidean Algorithm?

The Extended Euclidean Algorithm is an extension of the standard Euclidean Algorithm (which finds GCD by repeated division). The extended version also computes the Bezout coefficients x, y such that a·x + b·y = GCD(a, b). It runs in O(log min(a, b)) time. When GCD(a, b) = 1, the coefficient x is the modular inverse of a modulo b. This is critical for CRT, RSA, and many other algorithms.

Where is CRT used in real life?

CRT has many real-world applications: (1) RSA cryptography uses CRT to speed up decryption by ~4×. (2) Astronomy — computing when calendar cycles (e.g., 19-year Metonic cycle) align. (3) Error-correcting codes — redundant residue number systems reconstruct data from partial information. (4) Parallel computation — residue number systems enable carry-free, parallel arithmetic on large numbers. (5) Secret sharing schemes — distributing secret keys among multiple parties.