Chinese Remainder Theorem Calculator

What is the Chinese Remainder Theorem?

The Chinese Remainder Theorem (CRT) is a fundamental result in number theory that describes the conditions under which a system of simultaneous congruences has a unique solution. First documented by the Chinese mathematician Sun Tzu in the 3rd century AD, the theorem states that if you know the remainders of an integer when divided by several pairwise coprime moduli, you can uniquely determine that integer modulo the product of those moduli.

In modern terms, the Chinese Remainder Theorem solves for $x$ given a system of congruences:

$$x \equiv a_1 \pmod{n_1}$$ $$x \equiv a_2 \pmod{n_2}$$ $$\vdots$$ $$x \equiv a_k \pmod{n_k}$$

where the moduli $n_1, n_2, \ldots, n_k$ are pairwise coprime (meaning $\gcd(n_i, n_j) = 1$ for $i \neq j$). Under these conditions, there exists a unique solution $x$ modulo $N = n_1 \cdot n_2 \cdot \ldots \cdot n_k$.

The Chinese Remainder Theorem Formula

The solution to the system of congruences is given by:

$$x \equiv \sum_{i=1}^{k} a_i \cdot N_i \cdot M_i \pmod{N}$$

where:

• $N = \prod_{i=1}^{k} n_i$ is the product of all moduli
• $N_i = N / n_i$ is the product of all moduli except $n_i$
• $M_i$ is the modular multiplicative inverse of $N_i$ modulo $n_i$, satisfying $N_i \cdot M_i \equiv 1 \pmod{n_i}$
• $a_i$ is the given remainder for modulus $n_i$

Each term $a_i \cdot N_i \cdot M_i \equiv a_i \pmod{n_i}$ because $N_i \cdot M_i \equiv 1 \pmod{n_i}$, and $a_j \cdot N_j \cdot M_j \equiv 0 \pmod{n_i}$ for $j \neq i$ since $n_i$ divides $N_j$.

Step-by-Step Example

Consider the system:

$$x \equiv 2 \pmod{3}$$ $$x \equiv 3 \pmod{5}$$ $$x \equiv 2 \pmod{7}$$

Step 1: Compute $N = 3 \times 5 \times 7 = 105$.

Step 2: Compute $N_i$ for each modulus:

• $N_1 = 105 / 3 = 35$
• $N_2 = 105 / 5 = 21$
• $N_3 = 105 / 7 = 15$

Step 3: Find the modular inverses $M_i$ such that $N_i \cdot M_i \equiv 1 \pmod{n_i}$:

• $35 \cdot M_1 \equiv 1 \pmod{3} \implies 2 \cdot M_1 \equiv 1 \pmod{3} \implies M_1 = 2$
• $21 \cdot M_2 \equiv 1 \pmod{5} \implies 1 \cdot M_2 \equiv 1 \pmod{5} \implies M_2 = 1$
• $15 \cdot M_3 \equiv 1 \pmod{7} \implies 1 \cdot M_3 \equiv 1 \pmod{7} \implies M_3 = 1$

Step 4: Compute the solution:

$$x = (2 \times 35 \times 2) + (3 \times 21 \times 1) + (2 \times 15 \times 1) = 140 + 63 + 30 = 233$$ $$x \equiv 233 \pmod{105} = 233 - 2 \times 105 = 23$$

Therefore, $x \equiv 23 \pmod{105}$ is the unique solution. You can verify: $23 \div 3 = 7$ R $2$, $23 \div 5 = 4$ R $3$, $23 \div 7 = 3$ R $2$.

Applications of the Chinese Remainder Theorem

The Chinese Remainder Theorem has numerous practical applications across mathematics and computer science:

• RSA Cryptography: CRT accelerates RSA decryption by splitting the computation modulo $p$ and $q$ separately, then recombining the results. This makes decryption roughly 4 times faster.
• Large Integer Arithmetic: CRT enables the use of residue number systems (RNS), where large integers are represented by their remainders modulo several small, pairwise coprime moduli. Arithmetic operations can then be performed independently on each residue in parallel.
• Secret Sharing: CRT-based secret sharing schemes split a secret into shares such that a threshold number of shares can reconstruct the secret, but fewer shares reveal nothing.
• Computer Science: CRT is used in error detection and correction codes, fast Fourier transforms, and solving systems of linear congruences in competitive programming.

When Do the Conditions Fail?

The Chinese Remainder Theorem requires the moduli to be pairwise coprime. If two or more moduli share a common factor greater than 1, the system may have no solution or multiple solutions. For example:

$$x \equiv 1 \pmod{4}$$ $$x \equiv 3 \pmod{6}$$

Since $\gcd(4, 6) = 2 \neq 1$, this system has no solution. Learn more about the conditions for solvability with our Extended Euclidean Algorithm Calculator.

Related Modular Arithmetic Tools

Understanding the Chinese Remainder Theorem requires familiarity with modular arithmetic concepts. Explore these related tools:

• Extended Euclidean Algorithm Calculator finds $\gcd(a, b)$ and the coefficients for Bezout's identity, essential for computing modular inverses.
• Modulo Calculator computes $a \bmod b$ for any pair of numbers, the foundation of all modular arithmetic.
• Euler's Totient Function Calculator computes $\phi(n)$, the count of numbers coprime to $n$, used in RSA key generation.
• Modular Multiplicative Inverse Calculator finds $a^{-1} \pmod{m}$, a key component of the CRT solution formula.

Frequently Asked Questions

What does pairwise coprime mean?

A set of integers is pairwise coprime if every pair of numbers in the set has a greatest common divisor of 1. For example, 3, 5, and 7 are pairwise coprime because $\gcd(3,5) = \gcd(3,7) = \gcd(5,7) = 1$. This condition is essential for the Chinese Remainder Theorem to guarantee a unique solution.

Can the Chinese Remainder Theorem handle more than two congruences?

Yes, the Chinese Remainder Theorem works for any number of congruences as long as the moduli are pairwise coprime. The solution formula scales naturally: compute $N$ as the product of all moduli, then for each congruence compute $N_i$, find the modular inverse $M_i$, and sum the terms $a_i \cdot N_i \cdot M_i$. This calculator supports up to 10 simultaneous congruences.

What happens if the moduli are not coprime?

If the moduli share a common factor, the system may have no solution or infinitely many solutions. A solution exists only if the congruences are compatible: for any pair $i, j$, we must have $a_i \equiv a_j \pmod{\gcd(n_i, n_j)}$. When this condition holds, the system can be reduced to an equivalent system with coprime moduli by factoring out the common factors.

How does CRT speed up RSA decryption?

In RSA, the modulus $n = p \cdot q$ is the product of two large primes. Instead of computing $m = c^d \bmod n$ directly, CRT splits the computation: compute $m_p = c^{d_p} \bmod p$ and $m_q = c^{d_q} \bmod q$ where $d_p = d \bmod (p-1)$ and $d_q = d \bmod (q-1)$, then recombine using CRT. Since $p$ and $q$ are half the bit length of $n$, each exponentiation is roughly 4 times faster, making CRT-based RSA decryption about 4 times faster overall.

Is the solution always unique?

The solution is unique modulo $N$, the product of all moduli. This means there are infinitely many solutions in the integers, but they all differ by multiples of $N$. For example, if the solution is $x \equiv 23 \pmod{105}$, then $23$, $128$, $233$, etc. are all valid solutions. The calculator typically returns the smallest non-negative solution.

How is CRT related to the modular multiplicative inverse?

The CRT solution formula requires computing the modular multiplicative inverse $M_i$ of $N_i$ modulo $n_i$ for each congruence. Without modular inverses, the terms $a_i \cdot N_i \cdot M_i$ cannot be evaluated. You can use our Modular Multiplicative Inverse Calculator to verify these values independently.