Use this Chinese Remainder Theorem Solver to enter values, adjust options, and review results in a compact responsive workspace.
Results are calculated automatically as you enter data.
| Residue a | Modulus m |
|---|
Use the import modal to paste multiple congruences at once.
▼ See explanations and tips below ▼
The Chinese Remainder Theorem is a result in modular arithmetic. It helps solve systems where the same unknown integer has several different remainders when divided by different moduli.
A typical system looks like this:
Each line says something about the remainder of \(x\). For example, \(x \equiv 2 \pmod{3}\) means that \(x\) leaves a remainder of \(2\) when divided by \(3\).
In its standard form, the theorem says that if the moduli \(m_1, m_2, \ldots, m_n\) are pairwise coprime, then the system has one solution modulo the product \(m_1m_2\cdots m_n\). In other words, there is one residue class that satisfies all the congruences, and every solution differs from that residue by a multiple of the combined modulus.
The generalized version extends the idea to some systems where the moduli are not pairwise coprime. In that case, the system may still have a solution, but only when the residues are compatible with the common factors of the moduli.
The theorem is useful because it turns several remainder conditions into one compact answer. Instead of listing many congruences separately, you can combine them into a single congruence:
That form is easier to interpret, compare, and reuse.
The Chinese Remainder Theorem is common in elementary number theory, discrete mathematics, and modular arithmetic problems. It also appears in computational settings where a calculation can be split into smaller modular calculations and then recombined.
Even in simple word problems, the theorem gives a clean way to handle repeated cycles. If a number must fit several repeating patterns at the same time, a CRT-style congruence system is often the natural mathematical model.
The standard CRT starts with pairwise coprime moduli. For example, \(3\), \(5\), and \(7\) are pairwise coprime because every pair has greatest common divisor \(1\).
For pairwise coprime moduli, the combined modulus is the product:
The result is unique modulo \(M\). That does not mean there is only one integer solution. It means there is one solution class:
where \(k\) can be any integer.
For two congruences, the generalized method can be understood through a simple reduction. Suppose you want to solve:
The first congruence means \(x\) can be written as:
Substitute that into the second congruence:
Then subtract \(a\):
This is a linear congruence. Let:
A solution exists only when \(b-a\) is divisible by \(g\):
If that condition fails, the two congruences contradict each other. If it holds, the pair can be combined into one congruence modulo:
After combining one pair, the same idea can be repeated with the next congruence until the system is reduced to one final congruence.
Solve:
The moduli \(3\), \(5\), and \(7\) are pairwise coprime, so the combined modulus is:
Testing or applying the CRT gives:
Check the result:
So every solution has the form:
where \(k\) is any integer.
Non-coprime moduli do not automatically mean failure. Consider:
The moduli are not coprime because:
Now compare the residues:
Since \(6\) is divisible by \(2\), the congruences are compatible.
Start with \(x = 2 + 6t\) and substitute into the second congruence:
Divide by the common factor \(2\):
The inverse of \(3\) modulo \(5\) is \(2\), so:
Using \(t=1\) gives:
The combined modulus is:
So the solution is:
Now consider:
The greatest common divisor is:
The difference between the residues is:
Since \(1\) is not divisible by \(2\), the two conditions are incompatible. There is no integer that is both congruent to \(1\) modulo \(4\) and congruent to \(2\) modulo \(6\).
A result such as:
means that \(r\) is the least nonnegative residue of the solution class and \(M\) is the combined modulus. Every integer solution is obtained by adding or subtracting multiples of \(M\):
where \(k\) is any integer.
The combined modulus is the period of the answer. Once one solution is known, the next larger solution is \(M\) units away, and the next smaller solution is also \(M\) units away.
The smallest positive solution is usually \(r\), but there is one important exception. If the least nonnegative residue is \(0\), then the smallest positive solution is \(M\), not \(0\), because \(0\) is not positive.
If the result says the moduli are pairwise coprime, the standard Chinese Remainder Theorem applies directly. If the moduli are not pairwise coprime, the system can still have a valid solution when the residues agree modulo the relevant greatest common divisors.
An incompatibility message means the congruences do not have a common integer solution. In practical terms, at least two of the remainder conditions require different answers modulo a shared factor.
Use the Chinese Remainder Theorem when you need to combine several remainder conditions for the same unknown integer.
Common use cases include:
The theorem is most helpful when each condition is naturally written as a congruence. If the problem involves inequalities, real numbers, measurement error, or approximate data, the CRT may not be the right tool without additional modeling.
The CRT is an integer theorem. The residues and moduli should be integers, and each modulus should be positive. A modulus of \(0\) or a negative modulus is not valid.
This calculator treats the result as exact. It does not round decimal values, because the calculation is based on integer arithmetic. Entered residues are reduced to their least nonnegative form, so a residue outside the usual range still represents the same congruence class after normalization.
Type integer inputs plainly, such as 3 or -3. Decimal values, fractions, scientific notation such as 1e6, and explicit leading plus signs such as +3 are not supported.
At least two congruences are needed for a system. A single congruence is already a solution class, so there is nothing to combine.
For non-coprime moduli, a solution exists only when the residue conditions are compatible with the shared factors. If the compatibility test fails, there is no combined congruence to report.
Very large systems can produce very large combined moduli. The algebraic result can still be exact, but visual residue grids are only practical for small combined moduli. This calculator shows a full residue grid only when the combined modulus is at most \(72\); for larger combined moduli, viewing sample solution values is usually clearer than trying to display the whole residue cycle.
x ≡ 2 (mod 3), x == 2 mod 3, x = 2 mod 3, 2, 3, or 2 3.
No. The standard version requires the moduli to be pairwise coprime. Prime moduli are one way to guarantee that, but composite moduli can also be pairwise coprime.
Yes. A non-coprime system can have a solution when the residues agree modulo the greatest common divisor of the moduli involved. If the residues disagree modulo a shared factor, the system has no common solution.
It means every solution is found by choosing an integer value for \(k\). Positive, negative, and zero values of \(k\) all give valid solutions in the same congruence class.
When moduli are pairwise coprime, their least common multiple equals their product. When moduli share factors, the least common multiple is smaller than the product, and it becomes the period of the combined solution class when a compatible solution exists.
Negative residues are another way to name the same congruence class. For example, \(-1 \pmod{5}\) is the same as \(4 \pmod{5}\), so a solver can normalize \(-1\) to \(4\) before combining congruences.
A no-solution result means the congruences conflict. For two congruences, this happens when the difference between the residues is not divisible by the greatest common divisor of the moduli.
Books and Open Textbooks
Online Educational and Technical Sources