Chinese Remainder Theorem Calculator

Chinese Remainder Theorem Solver

Chinese Remainder Theorem Formula

Formula

\[ x \equiv a_1 \pmod{n_1} \\ x \equiv a_2 \pmod{n_2} \\ \vdots \\ x \equiv a_k \pmod{n_k} \\[1.5em] N = n_1 \cdot n_2 \cdots n_k, \quad N_i = \frac{N}{n_i}, \quad y_i \equiv N_i^{-1} \pmod{n_i} \\[1.5em] x \equiv \sum_{i=1}^{k} a_i \, N_i \, y_i \pmod{N} \]

Where:

\(a_i\) — the remainders (the values \(x\) must be congruent to)
\(n_i\) — the moduli, which must be pairwise coprime (their greatest common divisor is 1 for any two of them)
\(N\) — the product of all moduli, which equals their least common multiple when they are coprime
\(N_i\) — the product of all moduli except \(n_i\)
\(y_i\) — the modular inverse of \(N_i\) modulo \(n_i\), i.e. the number with \(N_i y_i \equiv 1 \pmod{n_i}\)
\(x\) — the unique solution modulo \(N\)

The theorem states that when the moduli are pairwise coprime, the system has exactly one solution in the range \(0 \le x < N\). The formula builds this solution by combining each remainder with the inverse of the corresponding partial product.

Chinese Remainder Theorem – Calculation Example

Example: find \(x\) such that \(x \equiv 2 \pmod{3}\) and \(x \equiv 3 \pmod{5}\) — these are the calculator's default values.

\[ N = 3 \times 5 = 15 \]

\[ N_1 = \frac{15}{3} = 5, \quad y_1 = 2 \; (\text{since } 5 \cdot 2 = 10 \equiv 1 \pmod{3}) \]

\[ N_2 = \frac{15}{5} = 3, \quad y_2 = 2 \; (\text{since } 3 \cdot 2 = 6 \equiv 1 \pmod{5}) \]

\[ x \equiv (2 \cdot 5 \cdot 2) + (3 \cdot 3 \cdot 2) \pmod{15} \equiv 20 + 18 = 38 \equiv 8 \pmod{15} \]

Result: \(x = 8\) modulo \(15\). Indeed, \(8 \div 3 = 2\) remainder \(2\) and \(8 \div 5 = 1\) remainder \(3\), so both congruences hold. The next solution is \(8 + 15 = 23\), then \(38\), and so on.

How to Use the Calculator

Enter the Number of congruences (at least 2). More remainder/modulus pairs appear automatically.
For the first congruence, type the remainder into remainder 1 (\(a_1\)) and the modulus into modulus 1 (\(n_1\)).
Repeat for remainder 2 / modulus 2 and any additional pairs.
Read the Smallest non-negative solution \(x\) and the Modulo (LCM of moduli) \(N\). Every number of the form \(x + kN\) (\(k = 0, 1, 2, \dots\)) also satisfies the system.

What Is the Chinese Remainder Theorem?

The Chinese Remainder Theorem (CRT) is a classical result in number theory, first described by the Chinese mathematician Sunzi around the 3rd–5th century CE. It answers the question: given several divisors and the remainders left after dividing an unknown number by each of them, can the number be recovered? The theorem says yes — provided the moduli are pairwise coprime — and the answer is unique within a range whose length is the product of all the moduli.

A concrete way to picture it: if an egg basket holds \(x\) eggs, and counting them 3 at a time leaves 2, while counting 5 at a time leaves 3, then \(x \equiv 2 \pmod{3}\) and \(x \equiv 3 \pmod{5}\). The CRT pins \(x\) down uniquely modulo 15 — in this case \(x = 8, 23, 38, \dots\)

The theorem matters because it shows that a system of many small congruences is equivalent to one congruence with a large modulus. This lets you replace arithmetic with a huge modulus by parallel arithmetic with several small, convenient moduli, then recombine the results. The recombination step uses modular inverses, which you can compute separately with the Multiplicative Inverse Modulo calculator; inverses of this kind are also related to Fermat's Little Theorem and Euler's Theorem.

Interpreting the Result

The calculator returns the smallest non-negative solution \(x\) and the combined modulus \(N\). The full solution set is \(x, x + N, x + 2N, \dots\), and if negative answers make sense in your problem, \(x - N\) and smaller values work too. Because the solution is unique modulo \(N\), two different inputs that produce the same \(x \pmod{N}\) describe exactly the same system.

Assumptions and Limitations

Pairwise coprime moduli are required. Every pair of moduli must share no common factor greater than 1; otherwise the calculator reports an error. If two moduli are, say, 4 and 6 (both divisible by 2), the system may have no solution at all, or several solutions modulo their LCM.
Consistency of the system. Even with coprime moduli the theorem always gives a solution — that is the strength of the CRT. Conflicts between congruences can only arise when the coprimality condition is broken.
Remainders may exceed the modulus. An input like \(a = 7, n = 5\) is treated as \(7 \equiv 2 \pmod 5\); the calculator reduces the final answer modulo \(N\) automatically.
Moduli must be positive integers. Values of 0 or negative numbers are rejected.
Large systems. Because \(N\) is the product of all moduli, it grows very quickly. With many moduli, the numbers involved can exceed the range where standard floating-point arithmetic is exact.

Where the CRT Is Used

Beyond pure number theory, the CRT is a working tool in several fields. In cryptography it speeds up RSA decryption by computing the result modulo each prime factor separately and recombining; it also underpins threshold schemes such as Shamir's Secret Sharing. In computer science, it enables residue number systems that perform additions and multiplications in parallel on small moduli, and it appears in hashing, scheduling, and calendar calculations — the classic "counting soldiers by rows" problems that originally motivated Sunzi's work.

Frequently Asked Questions

How can I solve a CRT system by hand without the formula?

For two congruences you can use substitution: take the first, so x = a₁ + k·n₁ for integers \(k\). Substitute into the second congruence, \(a_1 + k n_1 \equiv a_2 \pmod{n_2}\), and solve for \(k\) by finding the inverse of \(n_1\) modulo \(n_2\). Then plug \(k\) back to get \(x\), and reduce modulo \(n_1 n_2\). This successive substitution method works for any number of congruences, solving them two at a time.

What happens if the moduli are not pairwise coprime?

When two moduli share a common factor, the system may be inconsistent and have no solution at all. A solution exists only if the remainders are compatible: for every pair, \(a_i \equiv a_j \pmod{\gcd(n_i, n_j)}\). If they are compatible, the solution is still unique, but only modulo the least common multiple of the moduli instead of their product. The coprimality requirement is what guarantees a solution always exists, which is why this calculator rejects such inputs.

Why is the solution unique, and how do I find all other solutions?

Uniqueness comes from the fact that if two numbers \(x\) and \(x'\) both satisfy the system, their difference is divisible by every modulus, hence by their product \(N\) (since they are coprime). So \(x \equiv x' \pmod{N}\), meaning there is exactly one solution in \(0 \le x < N\). All other solutions are \(x + kN\) for any integer \(k\), including negative values like \(x - N\) if your problem allows them.

Can remainders be negative or larger than the modulus?

Yes. A remainder larger than its modulus is automatically reduced — for example, \(a = 7\) with \(n = 5\) is the same as \(a = 2\). Negative remainders also work: \(x \equiv -1 \pmod{5}\) means the same as \(x \equiv 4 \pmod{5}\). The final answer is always normalized to the smallest non-negative representative, in the range \(0 \le x < N\).

How do I find the modular inverse by hand?

Use the extended Euclidean algorithm: run the ordinary Euclidean algorithm on \(N_i\) and \(n_i\), then work backwards to express \(\gcd = 1\) as \(uN_i + vn_i\). The coefficient \(u\) satisfies \(uN_i \equiv 1 \pmod{n_i}\), so \(y_i = u \bmod n_i\). For a prime modulus \(p\) you can also use Fermat's Little Theorem: \(y_i \equiv N_i^{p-2} \pmod{p}\).

What are common mistakes when using the Chinese Remainder Theorem?

The most frequent errors are: using moduli that are not pairwise coprime (e.g. 4 and 6, which share the factor 2); mixing up the remainder and modulus fields when entering data; forgetting that the answer is a class of solutions, not a single number; and entering a modulus of 1, which is technically allowed but adds no information. Also check that your remainders match your problem — \(x \equiv 2 \pmod{3}\) is not the same as \(x \equiv 3 \pmod{2}\).

Is there a quick way to verify the calculator's answer?

Yes — simply divide the answer by each modulus and check the remainders. If the result is \(x\), verify that \(x \bmod n_i = a_i \bmod n_i\) for every congruence in your system. A second check: compute \(x \bmod N\) using a different method, such as successive substitution, and confirm you get the same value. If both checks pass, the solution is correct, since uniqueness modulo \(N\) guarantees there is no other answer in the range.