Chinese Remainder Theorem

Calculator for solving congruence systems using the Chinese Remainder Theorem

Chinese Remainder Calculator

Chinese Remainder Theorem

Finds a number x that simultaneously satisfies multiple congruences: x ≡ a₁ (mod m₁), x ≡ a₂ (mod m₂), ... where the moduli are pairwise coprime

Important condition

The moduli must be pairwise coprime, i.e. their greatest common divisor (gcd) must be 1.

Divisors (moduli)
Enter each divisor on a new line
Remainders
Enter each remainder on a new line
Input format: One value per line or separated by semicolons/spaces
Chinese Remainder Result
Enter divisors and remainders
The result is the smallest positive integer that satisfies all congruences

CRT Info

Chinese Remainder Theorem

Unique solution: When the moduli are pairwise coprime

Congruence Unique Coprime

Condition: gcd(mᵢ, mⱼ) = 1 for i ≠ j
Solution: x ≡ ∑ aᵢMᵢyᵢ (mod M)

Examples
x ≡ 2 (mod 3), x ≡ 3 (mod 4)
→ x = 11
x ≡ 1 (mod 5), x ≡ 3 (mod 7)
→ x = 31
Input format
New line: One value per line
Semicolon: 3;4;5
Space: 3 4 5
In number theory, the Chinese Remainder Theorem states: if you know the remainders and the divisors (moduli) of dividing an integer by several integers, you can determine the dividend uniquely (modulo the product) provided the divisors are pairwise coprime.
Pairwise coprime means there is no natural number greater than 1 that divides both numbers.


Mathematical foundations of the Chinese Remainder Theorem

Main statement
Given a system of congruences:
\[\begin{align} x &\equiv a_1 \pmod{m_1} \\ x &\equiv a_2 \pmod{m_2} \\ &\vdots \\ x &\equiv a_k \pmod{m_k} \end{align}\]

If the mᵢ are pairwise coprime, a unique solution exists modulo M = m₁·m₂·...·mₖ

Constructive solution
Solution formula:
\[x \equiv \sum_{i=1}^{k} a_i M_i y_i \pmod{M}\]
with \(M_i = \frac{M}{m_i}\) and \(M_i y_i \equiv 1 \pmod{m_i}\)

yᵢ is the modular inverse of Mᵢ modulo mᵢ

Coprimality
Condition for unique solution:
\[\gcd(m_i, m_j) = 1 \text{ for } i \neq j\]

The moduli must be pairwise coprime

Uniqueness
The solution is unique modulo:
\[M = \prod_{i=1}^{k} m_i\]

All other solutions differ by multiples of M

Step-by-step examples

Example 1: Simple system
Divisors: {3, 4, 5} Remainders: {2, 3, 1}
\[\begin{aligned} x &\equiv 2 \pmod{3} \\ x &\equiv 3 \pmod{4} \\ x &\equiv 1 \pmod{5} \end{aligned}\]
Solution: x = 11

Verification: 11÷3=3 remainder 2, 11÷4=2 remainder 3, 11÷5=2 remainder 1

Example 2: Two moduli
Divisors: {5, 7} Remainders: {1, 3}
\[\begin{aligned} x &\equiv 1 \pmod{5} \\ x &\equiv 3 \pmod{7} \end{aligned}\]
Solution: x = 31

Verification: 31÷5=6 remainder 1, 31÷7=4 remainder 3

Example 3: Larger numbers
Divisors: {13, 11, 7} Remainders: {12, 10, 6}
\[\begin{aligned} x &\equiv 12 \pmod{13} \\ x &\equiv 10 \pmod{11} \\ x &\equiv 6 \pmod{7} \end{aligned}\]
Solution: x = 1000

Verification: 1000÷13=76 R12, 1000÷11=90 R10, 1000÷7=142 R6

Solution algorithm
1. Coprimality

• Check gcd(mᵢ, mⱼ) = 1

• For all pairs i ≠ j

• Otherwise no unique solution

2. Compute M

• M = m₁ × m₂ × ... × mₖ

• Product of all moduli

• Mᵢ = M/mᵢ for each i

3. Find inverses

• Find yᵢ with Mᵢyᵢ ≡ 1 (mod mᵢ)

• Extended Euclidean algorithm

• Modular inverses

4. Solution

• x ≡ ∑ aᵢMᵢyᵢ (mod M)

• Sum all terms

• Reduce modulo M

The Chinese Remainder Theorem guarantees a unique solution in the range [0, M-1]

Applications of the Chinese Remainder Theorem

The Chinese Remainder Theorem has far-reaching applications in mathematics, computer science and cryptography:

Cryptography
  • RSA decryption with CRT optimization
  • Efficient modular exponentiation
  • Key distribution (secret sharing)
  • Elliptic curve cryptography
Number theory
  • Solving Diophantine equations
  • Simplifying modular arithmetic
  • Primality tests and factorization
  • Algebraic structures (rings, fields)
Computer science
  • Parallel computations in different moduli
  • Efficient algorithms for large numbers
  • Digital signal processing (FFT)
  • Error-correcting codes
Practical applications
  • Calendar calculations (different systems)
  • Shift scheduling with cycles
  • Inventory and logistics optimization
  • Resource allocation with periods

Chinese Remainder Theorem: Bridge between algebra and application

The Chinese Remainder Theorem is one of the most elegant and practically relevant results in number theory. This theorem, developed over 2000 years ago for calendar problems, connects abstract algebraic structures with concrete algorithmic applications. The central insight: under the condition of pairwise coprimality, complex congruence systems can be decomposed into simpler subproblems and recombined into a single unique solution. From modern cryptography to efficient computer arithmetic and signal processing, the CRT forms the mathematical foundation of many technologies in our digital world.

Summary

The Chinese Remainder Theorem exemplifies the power of mathematical abstraction: a problem from ancient mathematics becomes a key to modern technological breakthroughs. The elegant theory - congruence systems have unique solutions under coprimality conditions - transforms complex computations into efficient algorithms. From RSA decryption to parallel computations and error correction, the CRT shows how deep mathematical insights solve practical problems and enable new technical possibilities.