Math July 13, 2026 · 8 Min Read

Chinese Remainder Theorem Calculator – Guide & Formulas

Solve systems of simultaneous congruences using the Chinese Remainder Theorem. Find the smallest non-negative solution with step-by-step verification.

Solve systems of simultaneous congruences using the Chinese Remainder Theorem. Enter your remainders and moduli to find the smallest non-negative integer satisfying all conditions.

Key Takeaway

Use the free Chinese Remainder Theorem Calculator to solve systems of simultaneous congruences using the chinese remainder theorem. find the smallest non-negative solution with step-by-step verification. Get instant results with step-by-step explanations.

How to Use the Chinese Remainder Theorem Calculator

  1. Enter the number of congruences in your system (2 or more).
  2. For each congruence, enter the remainder (aᵢ) and the modulus (nᵢ).
  3. Ensure all moduli are pairwise coprime (GCD of any two moduli = 1) for a unique solution.
  4. Review the solution x, the step-by-step computation, and the verification showing x ≡ aᵢ (mod nᵢ) for each equation.

The Formula

Given pairwise coprime moduli n₁, n₂, ..., nₖ and remainders a₁, a₂, ..., aₖ, the solution is x = Σ(aᵢ × Mᵢ × yᵢ) mod N, where N = n₁ × n₂ × ... × nₖ, Mᵢ = N/nᵢ, and yᵢ = Mᵢ⁻¹ (mod nᵢ) is the modular inverse.

Variable Definitions

  • aᵢ: The remainder for the i-th congruence
  • nᵢ: The modulus for the i-th congruence (must be pairwise coprime)
  • N: The product of all moduli: N = n₁ × n₂ × ... × nₖ
  • Mᵢ: The partial product: Mᵢ = N / nᵢ
  • yᵢ: The modular inverse of Mᵢ modulo nᵢ, satisfying Mᵢ × yᵢ ≡ 1 (mod nᵢ)

Solving x ≡ 2 (mod 3), x ≡ 3 (mod 5), x ≡ 2 (mod 7)

Find the smallest non-negative x satisfying all three congruences.

  1. Step 1: Identify N = 3 × 5 × 7 = 105.
  2. Step 2: Compute partial products: M₁ = 105/3 = 35, M₂ = 105/5 = 21, M₃ = 105/7 = 15.
  3. Step 3: Find modular inverses: 35⁻¹ mod 3 = 2 (since 35×2=70≡1 mod 3), 21⁻¹ mod 5 = 1 (since 21×1=21≡1 mod 5), 15⁻¹ mod 7 = 1 (since 15×1=15≡1 mod 7).
  4. Step 4: Compute x = (2×35×2 + 3×21×1 + 2×15×1) mod 105 = (140 + 63 + 30) mod 105 = 233 mod 105 = 23.
  5. Step 5: Verify: 23 mod 3 = 2 ✓, 23 mod 5 = 3 ✓, 23 mod 7 = 2 ✓. The solution is x = 23.

Frequently Asked Questions

What is the Chinese Remainder Theorem?

The Chinese Remainder Theorem (CRT) states that if you have a system of simultaneous congruences with pairwise coprime moduli, there exists a unique solution modulo the product of all moduli.

What does "pairwise coprime" mean?

Pairwise coprime means the GCD of every pair of moduli is 1. For example, moduli 3, 5, and 7 are pairwise coprime because GCD(3,5)=1, GCD(3,7)=1, and GCD(5,7)=1.

What if the moduli are not pairwise coprime?

If moduli share a common factor, the system may have no solution or multiple solutions. The calculator checks for consistency. A solution exists only if a₁ ≡ a₂ (mod GCD(n₁, n₂)) for every pair.

How do I find the modular inverse?

The modular inverse of a modulo n is a number b such that a×b ≡ 1 (mod n). It exists when GCD(a,n) = 1 and can be found using the Extended Euclidean Algorithm.

What is the smallest non-negative solution?

The CRT guarantees a unique solution modulo N (the product of all moduli). The smallest non-negative solution is the remainder when the general solution is divided by N, giving a value in [0, N-1].

Can I solve with more than 3 congruences?

Yes. The CRT works for any number of congruences as long as all moduli are pairwise coprime. Simply add more rows of (remainder, modulus) pairs.

What are practical applications of CRT?

CRT is used in cryptography (RSA decryption), computer science (hash functions, parallel computing), calendar calculations, and error-correcting codes.

Who discovered the Chinese Remainder Theorem?

The theorem was first described by the Chinese mathematician Sun Zi in the 3rd century CE in his work "Sunzi Suanjing." It was later generalized by Indian and European mathematicians.