Chinese Remainder Theorem Calculator

Combine several modular clues into one answer

The Chinese remainder theorem, usually shortened to CRT, solves a very specific kind of puzzle: you do not know the exact value of an integer x, but you do know what remainder it leaves when divided by several different moduli. A statement such as x ≡ 2 (mod 5) means that when x is divided by 5, the remainder is 2. One such statement narrows the possibilities a little. Two or three such statements can pin the value down much more tightly. This calculator combines those clues and returns the smallest non-negative integer that satisfies every congruence at once, along with the modulus that describes the full repeating solution set.

That may sound abstract at first, but the idea shows up anywhere repeating cycles need to line up. You can think of moduli as cycle lengths and remainders as offsets inside those cycles. For example, one machine might repeat every 3 days, another every 5 days, and a third every 7 days. If you know each machine's position within its cycle, CRT tells you when all of those positions occur together. The same structure appears in clock arithmetic, residue number systems, calendar puzzles, cryptography, and many textbook number theory problems.

This page is written to help you use the calculator correctly, not just press a button. The important questions are: what each input means, why the moduli must be pairwise coprime for this version of the theorem, how the formula builds the answer, and how to read the result once it appears. If you understand those four points, the calculator becomes easy to trust and easy to check.

What you enter in the form

The form accepts either two congruences or three congruences. Each congruence has two pieces: a remainder and a modulus. The input labelled Remainder r₁ is the number you want x to leave behind after division by Modulus m₁. The second pair, r₂ and m₂, means the same thing for a different modulus. The third pair is optional. If you leave either r₃ or m₃ blank, the calculator simply ignores that third congruence and solves the two-equation system you supplied.

The moduli must be positive integers greater than 1, and in this calculator they must be pairwise coprime. That means every pair of moduli has greatest common divisor 1. So 3 and 5 are allowed, 4 and 9 are allowed, but 6 and 9 are not. When the moduli are pairwise coprime, CRT guarantees one unique solution modulo the product of the moduli. Some non-coprime systems still have solutions, but they need extra compatibility checks and can behave differently. This calculator intentionally focuses on the clean, standard case so the result is unambiguous.

Remainders are integers too. In everyday use, people often enter them in the standard range from 0 up to one less than the modulus, because that is the easiest way to read the system. For example, with modulus 5 the typical remainders are 0, 1, 2, 3, or 4. Larger or negative integers can still represent the same congruence class, though. For instance, −1 modulo 5 means the same thing as 4 modulo 5. The calculator's final normalization step reduces the combined answer into the usual smallest non-negative range.

How the calculator turns those inputs into a single congruence

At the broadest level, every calculator takes inputs and maps them to an output. That general idea can be written abstractly as a function. The MathML below is part of the original page and remains useful as a reminder that a result is produced from a collection of inputs:

For CRT, the inputs are the remainders and moduli, and the function is not a guess or approximation. It is a constructive theorem. The theorem starts from a system like the following, where each line describes the same unknown integer viewed through a different modulus:

If the moduli are pairwise coprime, define the combined modulus as the product of all moduli. Then build one contribution from each congruence. In that sense, CRT does look like a weighted sum of parts, which is why the second preserved MathML block still fits the story:

In the actual theorem, the weighted pieces are chosen very carefully so that each piece behaves like 1 under one modulus and 0 under the others. The construction used by this calculator is:

Here Nᵢ⁻¹ means the modular inverse of Mᵢ modulo mᵢ. The script on this page computes those inverses, adds the weighted terms, and then reduces the result modulo M so the displayed solution lies in the range from 0 to M − 1. The output is therefore the smallest non-negative representative of the full solution class.

Worked example you can verify by hand

Suppose you want to solve this system:

x ≡ 2 (mod 3), x ≡ 3 (mod 5), and x ≡ 2 (mod 7).

These moduli are pairwise coprime because gcd(3,5) = 1, gcd(3,7) = 1, and gcd(5,7) = 1. That means CRT applies directly. First multiply the moduli:

M = 3 × 5 × 7 = 105.

Next compute the partial products. For modulus 3, M₁ = 105 / 3 = 35. For modulus 5, M₂ = 105 / 5 = 21. For modulus 7, M₃ = 105 / 7 = 15. Now find modular inverses: 35 ≡ 2 (mod 3), and the inverse of 2 modulo 3 is 2 because 2 × 2 = 4 ≡ 1 (mod 3). For modulus 5, 21 ≡ 1 (mod 5), so the inverse is 1. For modulus 7, 15 ≡ 1 (mod 7), so the inverse is also 1.

Plug those pieces into the sum:

x ≡ 2·35·2 + 3·21·1 + 2·15·1 = 140 + 63 + 30 = 233 (mod 105).

Finally reduce 233 modulo 105. Since 233 − 210 = 23, the smallest non-negative solution is x ≡ 23 (mod 105). A quick check confirms it: 23 leaves remainder 2 when divided by 3, remainder 3 when divided by 5, and remainder 2 when divided by 7. So the calculator should return solution x ≡ 23 with modulus mod 105.

This example also explains how to interpret the result. The output is not only one number. It describes an infinite family of integers. If the calculator says x ≡ 23 (mod 105), then 23, 128, 233, 338, and every other number of the form 23 + 105k satisfy the same system. The calculator shows the smallest non-negative member of that family because it is the easiest representative to read.

How to read the result panel

After you press Solve, the results area shows two pieces of information: the solution and the combined modulus. Read them together. A line such as x ≡ 8 on its own would be incomplete, because modular arithmetic always depends on the modulus. When the result reads x ≡ 8 and mod 15, it means every solution differs from 8 by a multiple of 15. In other words, the pattern repeats every 15 integers.

A fast sanity check is to substitute the displayed solution back into each congruence. If the answer is x = 23, compute 23 mod 3, 23 mod 5, and 23 mod 7. Those three checks take only a few seconds and tell you whether the final answer matches the original system. When you are learning CRT, doing that check every time is worthwhile. It trains you to connect the calculator's output to the underlying meaning rather than treating the result as a black box.

The note below the table also matters. It reminds you that any integer of the form x + kM works, where M is the combined modulus and k is any integer. That sentence is the practical interpretation of the theorem. The calculator is not claiming there is only one integer that works. It is saying there is one residue class modulo M that works.

Important assumptions and edge cases

The biggest assumption is pairwise coprime moduli. If you enter 6 and 9, for example, the script will stop and show an error because the simple CRT construction used here no longer guarantees a unique answer modulo the product. Some such systems are inconsistent, and some have solutions but repeat with a different modulus. Rather than guess which special case you intended, the calculator asks for the standard setting where the theorem is cleanest.

The second assumption is that all inputs are integers. Congruences live in integer arithmetic, so fractions and decimal moduli do not make sense here. The number inputs on the form step by 1 for that reason. If your problem begins with a non-integer quantity, you usually need to reformulate it before using CRT.

The third assumption is interpretive rather than mathematical: a remainder is always read relative to its modulus. Saying remainder 4 is incomplete until you also say modulo 5, modulo 7, or modulo some other divisor. That is why the form uses pairs. The calculator does not know your intended cycle unless you tell it the modulus explicitly.

If you enter a remainder larger than its modulus, the math may still be valid, but the congruence can be easier to understand if you first reduce it. For example, remainder 17 modulo 5 is equivalent to remainder 2 modulo 5. Using the smaller representative does not change the solution set, but it makes hand-checking simpler. Likewise, negative remainders are legal in modular arithmetic, yet many readers find their equivalent non-negative versions easier to read.

Why people use CRT in practice

One common use is synchronization. Imagine several repeating processes that have different periods. One resets every 4 steps, another every 9, and a third every 5. If you know where each process sits in its cycle and want the next step count where all conditions happen together, CRT gives you the shared schedule. In that setting, the modulus is the cycle length and the remainder is the current offset.

Another use is efficient computation. In computer arithmetic and cryptography, large numbers can be split into smaller modular pieces, processed separately, and then recombined with CRT. That is one reason the theorem appears in discussions of RSA and residue number systems. The theorem is not merely a classroom trick; it is a reliable way to reconstruct a value from modular information.

It is also valuable as a thinking tool. The theorem teaches that several local constraints can collapse into one global description. Instead of carrying around three separate congruences forever, you can replace them with one combined congruence modulo the product of the pairwise coprime moduli. That compression is exactly what this calculator automates.