Chinese Remainder Theorem Calculator & Guide

Chinese Remainder Theorem Calculator

Solve systems of linear congruences and find a common solution using the Chinese Remainder Theorem.

CRT Calculator

Enter your congruences in the form x ≡ a (mod n).

Congruence 1: x ≡ a (mod n)

Modulus (n1)

Congruence 2: x ≡ a (mod n)

Modulus (n2)

Congruence 3: x ≡ a (mod n)

Modulus (n3)

Solution (x)

—

The Chinese Remainder Theorem finds a number x that satisfies multiple congruences simultaneously.

Intermediate Values & Steps

System of Congruences
Congruence	Remainder (aᵢ)	Modulus (nᵢ)
1	—	—
2	—	—
3	—	—

Visualizing Remainders across Moduli

What is the Chinese Remainder Theorem?

The Chinese Remainder Theorem (CRT) is a fundamental theorem in number theory that provides a unique solution to a system of simultaneous linear congruences with pairwise coprime moduli. In simpler terms, if you have several conditions of the form “a number leaves a specific remainder when divided by a specific number,” the CRT tells you if there’s a single number that satisfies all these conditions, and if so, what that number is, up to a certain modulus.

Who should use it?

Mathematicians and students studying number theory.
Computer scientists working on cryptography, algorithms, and coding theory.
Anyone interested in solving puzzles involving remainders and modular arithmetic.
Researchers in abstract algebra and related fields.

Common Misconceptions:

Misconception: The CRT always provides a single, specific number as a solution.
Reality: The CRT guarantees a unique solution modulo the product of the moduli. This means there are infinitely many solutions, all differing by multiples of this product.
Misconception: The CRT only works for three congruences.
Reality: The theorem can be extended to any finite number of congruences, provided their moduli are pairwise coprime.
Misconception: The theorem requires the moduli to be prime numbers.
Reality: The critical requirement is that the moduli must be *pairwise coprime* (their greatest common divisor is 1), not necessarily prime.

Chinese Remainder Theorem: Formula and Mathematical Explanation

The theorem addresses a system of congruences:

x ≡ a₁ (mod n₁)
x ≡ a₂ (mod n₂)
…
x ≡ a<0xE2><0x82><0x96> (mod n<0xE2><0x82><0x96>)

Where n₁, n₂, …, n<0xE2><0x82><0x96> are pairwise coprime integers (i.e., gcd(nᵢ, nⱼ) = 1 for all i ≠ j). The theorem states that there exists a unique solution modulo N, where N = n₁ * n₂ * … * n<0xE2><0x82><0x96>.

Derivation Steps:

Calculate the product of all moduli: N = n₁ * n₂ * … * n<0xE2><0x82><0x96>.
For each congruence i, calculate Nᵢ = N / nᵢ. This is the product of all moduli *except* nᵢ.
For each Nᵢ, find its modular multiplicative inverse yᵢ such that Nᵢ * yᵢ ≡ 1 (mod nᵢ). This yᵢ exists because gcd(Nᵢ, nᵢ) = 1 (since nᵢ is coprime to all other nⱼ that form Nᵢ). The Extended Euclidean Algorithm is typically used to find yᵢ.
The solution x is then given by the sum:
x = (a₁N₁y₁ + a₂N₂y₂ + … + a<0xE2><0x82><0x96>N<0xE2><0x82><0x96>y<0xE2><0x82><0x96>) mod N
The final result is x mod N. Any integer congruent to this value modulo N is also a solution.

Variable Explanations:

CRT Variables
Variable	Meaning	Unit	Typical Range / Condition
aᵢ	The remainder for the i-th congruence.	Integer	0 ≤ aᵢ < nᵢ
nᵢ	The modulus for the i-th congruence. Must be pairwise coprime.	Positive Integer	nᵢ > 1
N	The product of all moduli (N = n₁ * n₂ * … * n<0xE2><0x82><0x96>).	Integer	N > 0
Nᵢ	N / nᵢ (product of moduli except nᵢ).	Integer	Nᵢ > 0
yᵢ	The modular multiplicative inverse of Nᵢ modulo nᵢ (Nᵢ * yᵢ ≡ 1 (mod nᵢ)).	Integer	Exists if gcd(Nᵢ, nᵢ) = 1
x	The unique solution modulo N satisfying all congruences.	Integer	0 ≤ x < N

Practical Examples of the Chinese Remainder Theorem

The CRT, while abstract, has practical applications:

Example 1: Finding a Number of Eggs

A farmer is counting her eggs. When she groups them by 3, she has 2 left over. When she groups them by 5, she has 3 left over. When she groups them by 7, she has 2 left over. How many eggs does she have?

This translates to the system of congruences:

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

Here, a₁=2, n₁=3; a₂=3, n₂=5; a₃=2, n₃=7. The moduli (3, 5, 7) are pairwise coprime.

N = 3 * 5 * 7 = 105
N₁ = N / 3 = 105 / 3 = 35
N₂ = N / 5 = 105 / 5 = 21
N₃ = N / 7 = 105 / 7 = 15
Find y₁: 35y₁ ≡ 1 (mod 3). Since 35 ≡ 2 (mod 3), we have 2y₁ ≡ 1 (mod 3). y₁ = 2 (because 2*2 = 4 ≡ 1 mod 3).
Find y₂: 21y₂ ≡ 1 (mod 5). Since 21 ≡ 1 (mod 5), we have 1y₂ ≡ 1 (mod 5). y₂ = 1.
Find y₃: 15y₃ ≡ 1 (mod 7). Since 15 ≡ 1 (mod 7), we have 1y₃ ≡ 1 (mod 7). y₃ = 1.
x = (a₁N₁y₁ + a₂N₂y₂ + a₃N₃y₃) mod N
x = (2*35*2 + 3*21*1 + 2*15*1) mod 105
x = (140 + 63 + 30) mod 105
x = 233 mod 105
x = 23

Interpretation: The farmer has 23 eggs. This is the smallest positive number of eggs that satisfies all conditions. Other possible answers include 23 + 105 = 128, 23 + 2*105 = 233, etc.

Example 2: Cryptographic Application (Simplified)

Imagine a simplified secret sharing scheme. A secret number S can be represented by its remainders modulo several coprime numbers. If we know S ≡ 2 (mod 3) and S ≡ 3 (mod 5), we can find S.

System of congruences:

x ≡ 2 (mod 3)
x ≡ 3 (mod 5)

Here, a₁=2, n₁=3; a₂=3, n₂=5. Moduli are coprime.

N = 3 * 5 = 15
N₁ = N / 3 = 15 / 3 = 5
N₂ = N / 5 = 15 / 5 = 3
Find y₁: 5y₁ ≡ 1 (mod 3). Since 5 ≡ 2 (mod 3), we have 2y₁ ≡ 1 (mod 3). y₁ = 2.
Find y₂: 3y₂ ≡ 1 (mod 5). By trying values: 3*1=3, 3*2=6≡1 (mod 5). So, y₂ = 2.
x = (a₁N₁y₁ + a₂N₂y₂) mod N
x = (2*5*2 + 3*3*2) mod 15
x = (20 + 18) mod 15
x = 38 mod 15
x = 8

Interpretation: The secret number S is 8 (or any number congruent to 8 mod 15, like 23, 38, etc.). Knowing the remainders allows reconstruction of the secret within the range [0, N-1]. This principle is a building block in more complex cryptographic systems. This shows the power of modular arithmetic.

How to Use This Chinese Remainder Theorem Calculator

Using our CRT calculator is straightforward. Follow these simple steps:

Identify Congruences: Ensure your problem is a system of linear congruences. Each congruence should be in the form “x ≡ a (mod n)”, where ‘x’ is the unknown number, ‘a’ is the remainder, and ‘n’ is the modulus.
Input Values:
- For each congruence, enter the remainder (‘a’) in the first input field (e.g., ‘Congruence 1: x ≡ a (mod n)’ first box).
- Enter the modulus (‘n’) in the second input field for that congruence (e.g., ‘Congruence 1: x ≡ a (mod n)’ second box).
- The calculator supports up to three congruences by default. You can leave fields blank if you have fewer than three congruences, but ensure the ones you use are consecutive (e.g., fill 1 and 2, but not 3).
Check Moduli Coprimality: The Chinese Remainder Theorem requires that all moduli (n₁, n₂, n₃, etc.) must be pairwise coprime. This means the greatest common divisor (GCD) of any two different moduli must be 1. If your moduli are not pairwise coprime, the standard CRT formula doesn’t apply directly, and this calculator might produce incorrect results or indicate an error.
Click Calculate: Press the “Calculate” button.
Interpret Results:
- Main Result (Solution x): This is the smallest non-negative integer ‘x’ that satisfies all the entered congruences.
- Intermediate Values: The calculator displays N (product of moduli), Nᵢ (N/nᵢ), and yᵢ (modular inverse), which are crucial steps in the CRT calculation.
- Formula Explanation: A brief text explains the core idea of the CRT.
- Table of Congruences: This table summarizes the inputs you provided.
- Chart: The chart visually represents the remainders for each modulus, helping to conceptualize the solution space.
Copy Results: Use the “Copy Results” button to easily transfer the main solution, intermediate values, and key assumptions (like the pairwise coprime condition) to your notes or documents.
Reset: If you need to start over or clear the fields, click the “Reset” button. It will restore the default (empty or sensible) values.

Decision-Making Guidance: The primary output ‘x’ gives you the fundamental solution. Remember that any number of the form x + k*N (where N is the product of moduli and k is any integer) is also a valid solution. Choose the specific solution based on the context of your problem (e.g., the smallest positive integer).

Key Factors Affecting Chinese Remainder Theorem Results

While the mathematical process of the Chinese Remainder Theorem is deterministic, certain factors can influence how you set up and interpret the results:

Coprimality of Moduli: This is the most critical factor. If the moduli (nᵢ) are not pairwise coprime (gcd(nᵢ, nⱼ) ≠ 1 for some i ≠ j), the standard CRT doesn’t apply directly. A generalized version exists, but it might lead to no solution or a solution modulo lcm(n₁, n₂, …, n<0xE2><0x82><0x96>) instead of the product. Our calculator assumes pairwise coprimality.
Choice of Remainders (aᵢ): The remainders directly determine the specific solution. Different remainders will lead to different solutions modulo N. Ensure they are correctly identified from the problem statement.
Number of Congruences: The theorem works for any number of congruences. Adding more congruences (with pairwise coprime moduli) restricts the solution space further, leading to a smaller N (if previous moduli are kept) or potentially a different N.
Size of Moduli: Larger moduli lead to a larger overall product N. This means the unique solution found will be within a much wider range [0, N-1]. This is fundamental in cryptography, where large, coprime moduli are used to create large solution spaces for secrets.
Modular Multiplicative Inverse Existence: The calculation of yᵢ relies on the existence of the modular multiplicative inverse of Nᵢ modulo nᵢ. This inverse is guaranteed *only if* Nᵢ and nᵢ are coprime. Since Nᵢ is the product of all moduli except nᵢ, and all moduli are pairwise coprime, this condition is met.
Integer Overflow in Computation: For very large moduli, the product N and intermediate values Nᵢ can become extremely large, potentially exceeding the standard integer limits of a computing system. While this calculator uses standard JavaScript numbers, which have limits, advanced implementations require arbitrary-precision arithmetic libraries to handle such cases.
Problem Context: The “correct” solution often depends on the real-world problem. The CRT gives the smallest non-negative solution x. You might need x + N, x + 2N, etc., based on the practical constraints (e.g., finding the number of items manufactured within a specific timeframe).

Frequently Asked Questions (FAQ)

What happens if the moduli are not pairwise coprime?

If the moduli (n₁, n₂, …, n<0xE2><0x82><0x96>) are not pairwise coprime, the standard Chinese Remainder Theorem doesn’t directly apply. A solution might still exist, but it’s not guaranteed, and if it exists, it’s unique modulo the least common multiple (LCM) of the moduli, not their product. A generalized CRT handles these cases, often involving checking for consistency between congruences. Our calculator assumes pairwise coprime moduli for simplicity and standard application.

Can the remainders (aᵢ) be negative or larger than their modulus (nᵢ)?

Mathematically, a congruence like x ≡ 5 (mod 3) is equivalent to x ≡ 2 (mod 3) because 5 = 1*3 + 2. Similarly, x ≡ -1 (mod 3) is equivalent to x ≡ 2 (mod 3) because -1 = -1*3 + 2. For the CRT formula and our calculator, it’s best practice and usually required to use remainders ‘aᵢ’ such that 0 ≤ aᵢ < nᵢ. You can always normalize negative or oversized remainders before inputting them.

Is the solution found by the CRT always positive?

The standard CRT formula yields a result ‘x’ which is unique modulo N. The smallest non-negative solution is typically sought, meaning x is in the range [0, N-1]. If the calculation results in a negative value before the final modulo N operation, the modulo operation ensures the final result is non-negative. For example, -5 mod 3 is 1. Our calculator aims to provide the smallest non-negative integer solution.

What is the Extended Euclidean Algorithm used for in CRT?

The Extended Euclidean Algorithm is essential for finding the modular multiplicative inverse (yᵢ) required in the CRT formula. Specifically, for each i, it helps solve Nᵢyᵢ ≡ 1 (mod nᵢ). It finds integers yᵢ and k such that Nᵢyᵢ + nᵢk = gcd(Nᵢ, nᵢ). Since we need gcd(Nᵢ, nᵢ) = 1 for the inverse to exist, the algorithm finds yᵢ.

How is the CRT related to cryptography?

The CRT is a cornerstone in several cryptographic techniques. It’s used in RSA for efficient decryption (by performing computations modulo the prime factors p and q separately, then combining results using CRT), in secret sharing schemes (like Shamir’s Secret Sharing), and in constructing efficient algorithms for large number arithmetic needed in public-key cryptography. Its ability to reconstruct a large number from smaller pieces is key.

Can I use the CRT for more than three congruences?

Yes, absolutely. The Chinese Remainder Theorem is applicable to any finite number of congruences, as long as their moduli are pairwise coprime. Our calculator is limited to three for practical interface design, but the underlying mathematical principle extends indefinitely. For more congruences, you would continue the pattern: calculate N, Nᵢ, find yᵢ, and sum the terms aᵢNᵢyᵢ.

What does ‘pairwise coprime’ mean?

Pairwise coprime means that for any two distinct moduli in your set (nᵢ and nⱼ, where i ≠ j), their greatest common divisor (GCD) is 1. For example, the set {3, 5, 7} is pairwise coprime because gcd(3,5)=1, gcd(3,7)=1, and gcd(5,7)=1. However, the set {3, 5, 6} is not pairwise coprime because gcd(3,6)=3.

Does the order of congruences matter?

The final unique solution modulo N is independent of the order in which you list the congruences. The CRT formula is symmetric with respect to the congruences. However, for the calculation process, keeping track of which ‘aᵢ’ corresponds to which ‘nᵢ’ is crucial.