Chinese Remainder Theorem Calculator

Solve systems of congruences with this easy-to-use calculator.

Calculator

Number of Equations:

Result

Intermediate Values

What is the Chinese Remainder Theorem?

The Chinese Remainder Theorem (CRT) is a powerful result from number theory that provides a unique solution to a system of simultaneous linear congruences, provided the moduli are pairwise coprime. In simpler terms, if you know the remainders of a number when divided by several different integers, the theorem helps you find the number itself. This theorem has historical roots in ancient China, with its earliest known statement found in a 3rd-century manuscript by the mathematician Sunzi. It is not just an abstract mathematical curiosity; this chinese remainder theorem calculator demonstrates its practical application in solving complex problems. The theorem is widely used in modern applications such as cryptography (especially in RSA), computer science for handling large numbers, and signal processing.

Chinese Remainder Theorem Formula and Explanation

The theorem states that for a system of congruences:

x ≡ a₁ (mod n₁)
x ≡ a₂ (mod n₂)
…
x ≡ a_k (mod n_k)

If the moduli n₁, n₂, …, n_k are pairwise coprime (meaning the greatest common divisor of any two is 1), there exists a unique solution for x modulo N, where N is the product of all moduli (N = n₁ * n₂ * … * n_k).

The solution is found using the formula:

x = (a₁N₁y₁ + a₂N₂y₂ + … + a_kN_ky_k) mod N

Description of Variables in the CRT Formula
Variable	Meaning	Unit	Typical Range
x	The unique integer solution we are looking for.	Unitless Integer	0 to N-1
a_i	The remainder of the congruence.	Unitless Integer	0 to n_i-1
n_i	The modulus of the congruence; must be pairwise coprime.	Unitless Integer	Positive Integers > 1
N	The product of all moduli (N = n₁ * n₂ * … * n_k).	Unitless Integer	Positive Integer
N_i	Defined as N / n_i.	Unitless Integer	Positive Integer
y_i	The modular multiplicative inverse of N_i modulo n_i.	Unitless Integer	1 to n_i-1

Practical Examples

Example 1: Sunzi’s Original Problem

Let’s solve the classic problem stated by Sunzi: Find a number that leaves a remainder of 2 when divided by 3, a remainder of 3 when divided by 5, and a remainder of 2 when divided by 7.

Inputs:
- x ≡ 2 (mod 3)
- x ≡ 3 (mod 5)
- x ≡ 2 (mod 7)
Units: Not applicable (integers).
Results: Using our chinese remainder theorem calculator, we find that the smallest positive integer solution is 23. All solutions are of the form 23 + 105k, where k is an integer.

Example 2: A Scheduling Problem

Imagine you have three recurring events. Event A happens every 4 days, Event B every 5 days, and Event C every 9 days. Today, you observe that Event A will happen in 1 day, Event B will happen in 2 days, and Event C will happen in 8 days. How many days until all three events happen on the same day?

Inputs:
- x ≡ 1 (mod 4)
- x ≡ 2 (mod 5)
- x ≡ 8 (mod 9)
Units: Days.
Results: The calculator shows the solution is x ≡ 17 (mod 180). This means the events will coincide in 17 days, and then every 180 days thereafter.

How to Use This Chinese Remainder Theorem Calculator

Select Number of Equations: Choose how many congruence equations are in your system (from 2 to 5).
Enter Values: For each equation of the form x ≡ a (mod n), enter the remainder ‘a’ and the modulus ‘n’ into the respective input fields.
Check Units: The inputs are unitless integers. The moduli ‘n’ must be positive integers greater than 1.
Calculate: Click the “Calculate” button.
Interpret Results: The calculator will display the unique solution ‘x’ and the combined modulus ‘N’. It will also show key intermediate steps used in the calculation, such as the modular inverses. An error will be shown if the moduli are not pairwise coprime. For more on this, you can check our Modular Multiplicative Inverse Calculator.

Key Factors That Affect the Chinese Remainder Theorem

Pairwise Coprime Moduli: This is the most critical condition. The theorem only guarantees a unique solution if the greatest common divisor (GCD) of every pair of moduli is 1. If not, a solution may not exist.
Number of Congruences: More equations increase the complexity of the manual calculation but are easily handled by a chinese remainder theorem calculator.
Size of Moduli: Larger moduli result in a much larger solution space (modulo N), which is fundamental for applications like RSA cryptography.
Remainders (a_i values): The specific values of the remainders directly determine the final unique solution ‘x’.
Modular Multiplicative Inverse: The existence and calculation of this inverse for each N_i mod n_i is a cornerstone of the constructive proof and solution method. This often requires the Extended Euclidean Algorithm.
Integer Inputs: The theorem is defined for integers. Using non-integer or decimal values is not valid.

Frequently Asked Questions (FAQ)

What happens if the moduli are not coprime?

If the moduli are not pairwise coprime, a solution exists only if the congruences are consistent. For example, for the system x ≡ 1 (mod 2) and x ≡ 3 (mod 4), there is no solution. An odd number cannot have a remainder of 3 when divided by 4. Our chinese remainder theorem calculator will flag this as an error.

Is the solution always a positive number?

The theorem provides a unique solution within a complete system of residues modulo N. By convention, the smallest non-negative integer is usually presented as the primary answer. For example, if a calculation results in -5 (mod 12), the answer is typically given as 7.

Why is it called the “Chinese” Remainder Theorem?

The name acknowledges its first known appearance in the ancient Chinese mathematical text “Sunzi Suanjing” (The Mathematical Classic of Sunzi) from the 3rd to 5th century CE.

What are the main applications of the CRT?

Its main applications are in fields requiring large number arithmetic, such as cryptography (RSA), computer algebra systems, and signal processing (for reconstructing signals from undersampled data).

Can I use this calculator for congruences like 3x ≡ 4 (mod 5)?

This calculator is designed for systems where ‘x’ has a coefficient of 1. To solve 3x ≡ 4 (mod 5), you first need to find the modular multiplicative inverse of 3 (mod 5), which is 2. Multiplying both sides by 2 gives x ≡ 8 ≡ 3 (mod 5). You can then use x ≡ 3 (mod 5) in the chinese remainder theorem calculator.

How is the modular multiplicative inverse calculated?

It is typically calculated using the Extended Euclidean Algorithm, which finds integers x and y such that ax + by = gcd(a, b). When gcd(a, b) = 1, this gives the inverse.

Is there a limit to the number of equations?

In theory, no. As long as the moduli are pairwise coprime, you can have any number of equations. This calculator supports up to 5 for practical purposes.

What does “unique solution modulo N” mean?

It means there is only one integer ‘x’ between 0 and N-1 (inclusive) that satisfies all the congruences. All other solutions are found by adding or subtracting multiples of N to ‘x’.