Chinese Remainder Theorem Calculator

Find the shared residue for several congruences

The Chinese remainder theorem (CRT) resolves a particular modular-arithmetic question: an integer x is unknown, but its remainder after division by several moduli is known. The notation x ≡ 2 (mod 5), for example, says that division of x by 5 leaves 2. Each congruence describes a repeating set of possible integers. This calculator intersects two or three such sets and reports their least non-negative common value, together with the modulus that governs all later repetitions.

Chinese remainder theorem problems are often easiest to picture as synchronized cycles. A modulus is a cycle length, while a remainder identifies a position in that cycle. When several cycles have known positions, CRT identifies the values at which every stated position occurs simultaneously. This same structure occurs in clock arithmetic, scheduling puzzles, residue number systems, cryptographic computations, and elementary number theory exercises.

This Chinese remainder theorem guide focuses on the details that determine whether a result is meaningful: entering each residue-modulus pair, checking pairwise coprimality, understanding the constructive CRT sum, and interpreting the residue class returned by the calculator. With those points in view, the displayed result is straightforward to verify by substitution.

Chinese remainder theorem inputs: remainders and moduli

The Chinese remainder theorem form accepts either two or three congruences. A congruence contains a remainder and a modulus. Remainder r₁ specifies the value left after dividing x by Modulus m₁; r₂ and m₂ specify the second condition. The third pair is optional. If either third field is blank, the calculator uses the first two congruences only.

For this CRT calculator, moduli must be positive integers greater than 1 and must be pairwise coprime. In other words, every two moduli must have greatest common divisor 1. Moduli 3 and 5 qualify, as do 4 and 9; 6 and 9 do not. Under this condition, there is exactly one solution class modulo the product of the moduli. Systems with non-coprime moduli can sometimes be solved, but require compatibility tests outside the construction used on this page.

CRT remainders are integers as well. It is conventional to enter a remainder from 0 through one less than its modulus, because that gives the clearest description of the congruence. Equivalent values still describe the same class: −1 modulo 5 is equivalent to 4 modulo 5, and 17 modulo 5 is equivalent to 2 modulo 5. After combining the conditions, the calculator normalizes its answer into the least non-negative range.

How this CRT calculator constructs one congruence

The Chinese remainder theorem starts with congruences for the same unknown integer. For two inputs, use the first two lines below; when the optional pair is present, the third line is included as well:

For pairwise coprime moduli, CRT first forms the total modulus M, the product of every modulus in use. It then forms a partial product Mᵢ by omitting mᵢ from that product:

For each partial product, the script finds its modular inverse modulo the omitted modulus. Those inverse values make every term vanish under the other moduli while preserving its own required remainder. The resulting CRT construction is:

Here Nᵢ⁻¹ is the modular inverse of Mᵢ modulo mᵢ. The calculator adds these CRT terms and reduces the total modulo M. Its displayed solution therefore lies between 0 and M − 1, while still representing every integer that satisfies the supplied congruences.

Chinese remainder theorem example: residues 2, 3, and 2

To verify the calculator's CRT method by hand, solve x ≡ 2 (mod 3), x ≡ 3 (mod 5), and x ≡ 2 (mod 7).

The moduli are pairwise coprime: gcd(3,5) = 1, gcd(3,7) = 1, and gcd(5,7) = 1. Their product is M = 3 × 5 × 7 = 105. The partial products are M₁ = 35, M₂ = 21, and M₃ = 15.

Modulo 3, 35 is 2, whose inverse is 2. Modulo 5, 21 is 1, whose inverse is 1. Modulo 7, 15 is 1, whose inverse is also 1. The CRT sum is therefore x ≡ 2·35·2 + 3·21·1 + 2·15·1 = 233 (mod 105).

Reducing 233 modulo 105 gives 23, so the least non-negative solution is x ≡ 23 (mod 105). Direct substitution confirms it: 23 leaves remainders 2, 3, and 2 when divided by 3, 5, and 7 respectively. Entering these values in the calculator returns the same residue and combined modulus.

This CRT result represents an infinite sequence, not just the integer 23. Every value of the form 23 + 105k, where k is any integer, has the same three remainders. The least non-negative representative is displayed because it is the standard compact way to state the entire solution class.

Reading the combined CRT result

The Chinese remainder theorem result panel must be read as a residue together with its modulus. A solution shown as x ≡ 8 and mod 15 means that every acceptable integer differs from 8 by a multiple of 15. The combined modulus is the repetition interval for the complete system, not a separate unrelated output.

For a quick CRT check, divide the displayed solution by each original modulus and compare the remainders with the values entered. In the example above, checking 23 modulo 3, 5, and 7 immediately reproduces 2, 3, and 2. This substitution check is especially useful when translating a word problem about cycles into congruences.

The note below the results table expresses the same point algebraically: any integer of the form x + kM satisfies the system, with M equal to the combined modulus. CRT does not claim only one integer works; it identifies the one residue class that meets all of the stated modular conditions.

CRT assumptions and input edge cases

The central Chinese remainder theorem assumption on this page is pairwise coprimality. If moduli such as 6 and 9 are entered, the script reports an error because its product-modulus construction requires every pair to have gcd 1. Non-coprime congruences may be inconsistent or may have a solution with a different repeating modulus, so they are deliberately outside this calculator's scope.

CRT also uses integer arithmetic. Decimal or fractional moduli do not define the congruences handled here, and every remainder should be an integer. The form uses whole-number steps to reflect that requirement. A problem involving a non-integer physical quantity must be converted to an integer modular statement before CRT can be applied.

A remainder is meaningful only relative to its modulus. Remainder 4 has no complete interpretation until it is paired with a divisor such as 5 or 7. That is why each row of the form asks for both values rather than treating remainders as standalone inputs.

Although a remainder larger than its modulus or a negative remainder can describe a valid congruence, reducing it first often makes the setup easier to audit. For instance, 17 modulo 5 and 2 modulo 5 impose identical conditions. Using the smaller non-negative form does not change the solution set, but makes hand checks and comparisons clearer.

Where Chinese remainder theorem solutions are useful

Chinese remainder theorem calculations are useful for aligning repeating conditions. If separate processes have distinct pairwise coprime periods and known offsets, a CRT congruence gives the values at which those offsets coincide. In such a model, each modulus is a period and each remainder is the desired position within that period.

CRT is also used to recombine modular computations. In computer arithmetic and cryptography, a large computation can be performed in smaller residue systems and then reconstructed from the resulting congruences. This is why the theorem appears in discussions of residue number systems and some implementations of public-key cryptography.

More generally, the theorem turns several local remainder constraints into one global modular statement. Rather than carrying multiple congruences through later work, you can use the combined residue and product modulus returned by this calculator, provided the original moduli meet the pairwise-coprime condition.