Chinese Remainder Theorem Calculator

Solve simultaneous congruences when moduli are pairwise coprime. This educational calculator shows the formula, result, and step-by-step interpretation.

Computer ScienceCryptographyDiscrete Math

Calculator

Remainders aᵢ

Moduli mᵢ

What this calculator teaches

The Chinese Remainder Theorem combines modular conditions into one equivalent modular solution.

Use the result as a learning aid. For classwork, still show the formula and intermediate reasoning so the final answer is not just a black-box number.

How the Chinese Remainder Theorem Builds One Solution

The Chinese Remainder Theorem (CRT) replaces several compatible modular conditions with one repeating solution class. If the moduli m₁, m₂, ..., m_n are pairwise coprime, there is exactly one solution modulo M = m₁m₂...m_n. That means every integer satisfying all the congruences has the form x = x₀ + kM for some integer k.

A constructive solution uses M_i = M/m_i. Because M_i is coprime to m_i, it has a modular inverse y_i satisfying M_iy_i ≡ 1 (mod m_i). The sum Σa_iM_iy_i is then reduced modulo M. Each term is designed to reproduce one desired remainder while becoming 0 modulo every other modulus.

Step	Construction	Purpose
Combined modulus	`M = ∏mᵢ`	Sets the period of all solutions
Partial product	`Mᵢ = M/mᵢ`	Contains every modulus except mᵢ
Inverse	`Mᵢyᵢ ≡ 1 (mod mᵢ)`	Makes the ith term reproduce aᵢ

Pairwise coprimality is the clean textbook case used by this calculator. More general systems with non-coprime moduli can sometimes have solutions, but they require an additional consistency test and are outside this page's stated method.

A reliable CRT check is computationally simple: reduce the candidate solution modulo every original modulus. This is often faster than repeating the constructive derivation. Also report the combined modulus, because “x ≡ 13 (mod 20)” communicates both the smallest nonnegative representative and the entire infinite family 13+20k.

When hand-solving, reduce large or negative remainders first. For example, x ≡ 17 (mod 5) can be rewritten as x ≡ 2 (mod 5), and x ≡ -1 (mod 7) can be rewritten as x ≡ 6 (mod 7). Equivalent residues do not change the solution set.

Formula & Symbols

Concept	Formula or rule
Congruence	`x ≡ aᵢ (mod mᵢ)`
Solution modulus	`M = m₁m₂...mₙ`

Worked example

Example: x ≡ 2 mod 3, x ≡ 3 mod 5, x ≡ 2 mod 7 gives x ≡ 23 mod 105.

Example 2: x ≡ 1 (mod 4) and x ≡ 3 (mod 5) gives x ≡ 13 (mod 20). Indeed, 13 leaves remainders 1 and 3.

Example 3: x ≡ 2 (mod 5) and x ≡ 4 (mod 7) gives x ≡ 32 (mod 35).

Example 4: x ≡ 0 (mod 3) and x ≡ 1 (mod 4) gives x ≡ 9 (mod 12).

Example 5: x ≡ 5 (mod 7) and x ≡ 7 (mod 11) gives x ≡ 40 (mod 77).

Common mistakes

⚠️

Using the wrong input format

Keep lists comma separated, matrices as rows separated by semicolons, and modular inputs as integers.

⚠️

Ignoring assumptions

Some methods require positive probabilities, valid moduli, independent trials, or small educational input sizes.

⚠️

Checking only one congruence

A CRT answer must satisfy every original remainder condition. Substitute the final x into each modulus before accepting it.

⚠️

Forgetting that the solution repeats

x = 23 is not the only integer solution to x ≡ 23 (mod 105); 128, 233, and all values 23 + 105k are equivalent solutions.

FAQ

Can I use decimals?⌄

Most numerical calculators allow decimals, but modular arithmetic and coding-theory tools usually require integers or binary strings.

Is this for homework checking?⌄

Yes. The page is designed to show both the answer and the reasoning pattern.

Why does the result sometimes say approximate?⌄

Some probability, floating-point, and numerical methods naturally produce approximations.

Why must the moduli be pairwise coprime here?⌄

Pairwise coprimality guarantees that each partial product Mᵢ has an inverse modulo mᵢ and gives a unique solution class modulo the product M.

Can a remainder be negative?⌄

Yes mathematically. A negative remainder can be replaced by its equivalent least nonnegative residue, such as -1 ≡ 4 (mod 5).

How do I verify a CRT answer quickly?⌄

Compute the final x modulo each original modulus. Every result should equal the corresponding requested remainder after reducing both to equivalent residues.

What does “unique modulo M” mean?⌄

It means there is one residue class among 0 through M-1. Adding or subtracting any multiple of M produces another integer satisfying the same system.

Related calculators

These links will work after the calculators are registered in the final Math layout update.

Formula Explorer connections

Interpretation: This formula uses integer divisibility, modular arithmetic, finite fields or coding relationships. Assumption: Inputs are usually integers with specific modulus or coprimality requirements. Cryptographic examples are educational and not a substitute for vetted security libraries.

CRC Calculator →Diffie-Hellman Mathematics Calculator →Factorial Calculator →Math Formula Explorer →