Number TheoryMathCalculatorsModular Arithmetic

Chinese Remainder Theorem Calculator: Solve Modular Systems Step by Step

September 8, 2026·14 min read·Solvify Team

A Chinese remainder theorem calculator solves a system of simultaneous congruences — statements like x ≡ 2 (mod 3) and x ≡ 3 (mod 5) — by combining them into a single congruence modulo the product (or least common multiple) of the individual moduli. The method dates back roughly 1,500 years to the Chinese mathematical text Sunzi Suanjing, and today it underpins RSA cryptography optimizations, calendar calculations, and error-correcting codes, in addition to being a staple of discrete math and number theory courses. This guide walks through how the calculator works internally, how to check whether a system even has a solution, how to find the modular inverses the method depends on, two fully worked examples — one with pairwise coprime moduli and one without — plus common mistakes and practice problems.

01What Is the Chinese Remainder Theorem?
02How Does a Chinese Remainder Theorem Calculator Work?
03How Do You Check Whether Moduli Are Compatible?
04What Is a Modular Inverse and How Do You Find One?
05Worked Example: Solving Pairwise Coprime Congruences
06Worked Example: Reconciling Non-Coprime Moduli
07Reconstructing the Smallest Nonnegative Solution
08What Are the Most Common Chinese Remainder Theorem Mistakes?
09Practice Problems: Test Your Chinese Remainder Theorem Calculator Skills

What Is the Chinese Remainder Theorem?

The Chinese Remainder Theorem (CRT) says that if you have a system of congruences x ≡ a₁ (mod m₁), x ≡ a₂ (mod m₂), ..., x ≡ aₙ (mod mₙ), and the moduli m₁, m₂, ..., mₙ are pairwise coprime (every pair shares no common factor except 1), then there is exactly one solution for x modulo M, where M = m₁ × m₂ × ... × mₙ. The theorem gets its name from its earliest known appearance in the 3rd-to-5th-century Chinese text Sunzi Suanjing (Master Sun's Arithmetic Manual), which posed the now-classic puzzle: find a number that leaves remainder 2 when divided by 3, remainder 3 when divided by 5, and remainder 2 when divided by 7. That puzzle — and the CRT method that solves it — reappears constantly outside the classroom: RSA cryptography uses CRT to speed up decryption by working with smaller moduli instead of one huge one, computer scientists use it to represent large numbers as tuples of smaller residues for faster arithmetic, and calendar systems use it to reconcile cycles of different lengths (days of the week, days of the month, and leap-year cycles).

Chinese Remainder Theorem: for pairwise coprime moduli m₁, ..., mₙ, the system x ≡ aᵢ (mod mᵢ) has exactly one solution modulo M = m₁ × m₂ × ... × mₙ.

How Does a Chinese Remainder Theorem Calculator Work?

A Chinese remainder theorem calculator automates four stages that are tedious to track by hand once a system has three or more congruences, especially the modular inverse computations. Internally, it treats each congruence as a pair (aᵢ, mᵢ), confirms the moduli are usable together, and then builds the unique solution using a weighted sum rather than trial and error. Understanding these four stages is what lets you verify a calculator's output, or work the same problem by hand on an exam where no calculator is allowed.

1. Step 1: Check the moduli

Confirm every pair of moduli is coprime (gcd = 1). If any pair shares a common factor, the calculator switches to the compatibility check described in the next section instead of the standard formula.

2. Step 2: Compute the combined modulus M

Multiply all the moduli together: M = m₁ × m₂ × ... × mₙ. This is the modulus of the final, combined answer.

3. Step 3: Find each partial product and its modular inverse

For each congruence i, compute Mᵢ = M / mᵢ (the product of every modulus except mᵢ), then find the modular inverse of Mᵢ modulo mᵢ — call it yᵢ, where Mᵢ × yᵢ ≡ 1 (mod mᵢ).

4. Step 4: Combine and reduce

Sum aᵢ × Mᵢ × yᵢ across every congruence, then reduce that sum modulo M to get the unique smallest nonnegative solution x.

The formula behind every Chinese remainder theorem calculator: x ≡ Σ (aᵢ × Mᵢ × yᵢ) mod M, where Mᵢ = M/mᵢ and yᵢ is the modular inverse of Mᵢ mod mᵢ.

How Do You Check Whether Moduli Are Compatible?

The textbook version of the Chinese Remainder Theorem requires pairwise coprime moduli, but real systems — especially ones that show up in scheduling or cryptography problems — often have moduli that share factors. A generalized version of CRT still applies, but only if the system passes a compatibility check first: for every pair of congruences x ≡ aᵢ (mod mᵢ) and x ≡ aⱼ (mod mⱼ), the two must agree on the overlap, meaning aᵢ ≡ aⱼ (mod gcd(mᵢ, mⱼ)). If that check fails for even one pair, the system has no solution at all, no matter what else it says — and a good calculator reports this instead of returning a wrong number.

1. Step 1: Compute gcd(mᵢ, mⱼ) for each pair of moduli

For a two-congruence system, there's only one pair to check. For a three-congruence system, check all three pairs.

2. Step 2: Reduce both residues modulo that gcd

Take aᵢ mod gcd(mᵢ, mⱼ) and aⱼ mod gcd(mᵢ, mⱼ). If they match, the pair is compatible.

3. Step 3: Example of an incompatible system

Take x ≡ 1 (mod 4) and x ≡ 0 (mod 6). gcd(4, 6) = 2. Reduce: 1 mod 2 = 1, and 0 mod 2 = 0. Since 1 ≠ 0, no integer satisfies both congruences — the system has no solution, and a Chinese remainder theorem calculator should flag exactly this instead of forcing an answer.

Compatibility rule for non-coprime moduli: x ≡ aᵢ (mod mᵢ) and x ≡ aⱼ (mod mⱼ) can both be true only if aᵢ ≡ aⱼ (mod gcd(mᵢ, mⱼ)).

What Is a Modular Inverse and How Do You Find One?

The modular inverse of a number a modulo m is another number b such that a × b ≡ 1 (mod m) — it plays the same role that 1/a plays in ordinary division, but restricted to whole numbers within a fixed modulus. A modular inverse exists if and only if gcd(a, m) = 1, which is exactly why the standard Chinese Remainder Theorem requires pairwise coprime moduli: it guarantees every Mᵢ has an inverse mod mᵢ. The most reliable way to find a modular inverse by hand is the extended Euclidean algorithm, which runs the ordinary gcd algorithm forward and then works backward to express 1 as a combination of a and m.

1. Step 1: Run the Euclidean algorithm forward

Find the inverse of 4 mod 7. Divide repeatedly: 7 = 1×4 + 3, then 4 = 1×3 + 1, then 3 = 3×1 + 0. The remainders are 3, then 1, then 0, confirming gcd(4, 7) = 1, so an inverse exists.

2. Step 2: Work backward to isolate 1

From the second-to-last line, 1 = 4 − 1×3. Substitute 3 = 7 − 1×4 from the first line: 1 = 4 − 1×(7 − 1×4) = 2×4 − 1×7.

3. Step 3: Read off the inverse

The equation 1 = 2×4 − 1×7 means 2×4 ≡ 1 (mod 7), so the inverse of 4 mod 7 is 2. Quick check: 4 × 2 = 8 = 7 + 1, which is indeed ≡ 1 (mod 7).

For small moduli, it's often faster to test candidates directly: multiply a by 1, 2, 3, ... mod m until the product is 1. For larger moduli, the extended Euclidean algorithm is far more reliable.

Worked Example: Solving Pairwise Coprime Congruences

This is the classic Sunzi Suanjing problem: find x such that x ≡ 2 (mod 3), x ≡ 3 (mod 5), and x ≡ 2 (mod 7). The moduli 3, 5, and 7 are pairwise coprime, so the standard CRT formula applies directly.

1. Step 1: Compute M

M = 3 × 5 × 7 = 105.

2. Step 2: Compute each Mᵢ and its inverse

M₁ = 105/3 = 35. 35 mod 3 = 2, and the inverse of 2 mod 3 is 2 (since 2×2 = 4 ≡ 1 mod 3). M₂ = 105/5 = 21. 21 mod 5 = 1, and the inverse of 1 mod 5 is 1. M₃ = 105/7 = 15. 15 mod 7 = 1, and the inverse of 1 mod 7 is 1.

3. Step 3: Combine

x ≡ (a₁×M₁×y₁) + (a₂×M₂×y₂) + (a₃×M₃×y₃) mod M = (2×35×2) + (3×21×1) + (2×15×1) mod 105 = 140 + 63 + 30 mod 105 = 233 mod 105 = 23.

4. Step 4: Verify

23 ÷ 3 = 7 remainder 2 ✓. 23 ÷ 5 = 4 remainder 3 ✓. 23 ÷ 7 = 3 remainder 2 ✓. The smallest nonnegative solution is x = 23, and every other solution is 23 + 105k for any integer k.

x ≡ 23 (mod 105) — the same answer a Chinese remainder theorem calculator returns instantly, and the same puzzle that opened this branch of number theory over a thousand years ago.

Worked Example: Reconciling Non-Coprime Moduli

Now solve x ≡ 3 (mod 4) and x ≡ 1 (mod 6), where 4 and 6 are not coprime (they share a factor of 2). The standard formula from the pairwise-coprime example doesn't apply directly, but the system can still have a unique solution modulo the least common multiple of the moduli, provided it passes the compatibility check first.

1. Step 1: Check compatibility

gcd(4, 6) = 2. Reduce both residues: 3 mod 2 = 1, and 1 mod 2 = 1. They match, so the system is compatible and a solution exists.

2. Step 2: Find the combined modulus

Instead of multiplying 4 × 6 = 24, use the least common multiple: lcm(4, 6) = 12. The solution will be unique modulo 12, not 24.

3. Step 3: Substitute and solve

Write x = 4k + 3 from the first congruence, then substitute into the second: 4k + 3 ≡ 1 (mod 6), so 4k ≡ −2 ≡ 4 (mod 6). Both sides and the modulus share a factor of gcd(4, 6) = 2, so divide the entire congruence by 2: 2k ≡ 2 (mod 3). The inverse of 2 mod 3 is 2, so k ≡ 2×2 ≡ 1 (mod 3).

4. Step 4: Reconstruct x

k = 3j + 1 for any integer j, so x = 4(3j + 1) + 3 = 12j + 7. The smallest nonnegative solution is x = 7.

5. Step 5: Verify

7 mod 4 = 3 ✓. 7 mod 6 = 1 ✓. So x ≡ 7 (mod 12) is correct, and dividing the congruence by the shared factor — rather than ignoring it — is the step that makes non-coprime CRT work.

When moduli share a common factor, you can't use the pairwise-coprime formula as-is — you must divide the resulting congruence by gcd(mᵢ, mⱼ) before finding the inverse, or the inverse won't exist.

Reconstructing the Smallest Nonnegative Solution

Every Chinese remainder theorem system that passes its compatibility check has infinitely many integer solutions, not just one — but they're all congruent to each other modulo M (or modulo lcm(m₁, ..., mₙ) in the non-coprime case). By convention, a calculator reports the smallest nonnegative representative of that infinite family, the value x₀ satisfying 0 ≤ x₀ < M, because it's the single canonical answer that's easiest to state, compare, and verify. Every other solution is just x₀ plus or minus a multiple of M.

1. Reducing a negative intermediate sum

The weighted sum in Step 4 of the calculator method can come out negative if any residue aᵢ is negative or if a modular inverse was computed as a negative representative. If the sum is, say, S = −37 and M = 45, add M repeatedly until the result is nonnegative: −37 + 45 = 8, so the smallest nonnegative solution is x₀ = 8, not −37.

2. The full solution set

Once you have x₀, the complete solution set is every integer of the form x₀ + kM for k = ..., −2, −1, 0, 1, 2, .... In the Sunzi example above, that's 23, 128, 233, ... and also −82, −187, and so on — but 23 is the one you report unless a specific range is requested.

A negative or oversized intermediate result isn't wrong — it just hasn't been reduced yet. Add or subtract multiples of M until the value lands in [0, M).

What Are the Most Common Chinese Remainder Theorem Mistakes?

Most errors in CRT problems come from skipping a check rather than from a flawed final calculation, which is why it pays to slow down at the start of a problem rather than the end.

1. Applying the coprime formula to non-coprime moduli

If any two moduli share a factor, computing M as their straight product and looking for modular inverses the standard way will fail silently or produce a wrong answer — always check gcd(mᵢ, mⱼ) = 1 for every pair first.

2. Confusing a modular inverse with a regular reciprocal

The inverse of 4 mod 7 is 2, not 1/4 — modular inverses are whole numbers found via the extended Euclidean algorithm (or trial multiplication for small moduli), never fractions.

3. Not reducing negative numbers correctly modulo m

−2 mod 6 is 4, not −2 and not 2 — keep adding the modulus until the result is in the range [0, m). Truncating or taking the absolute value instead of adding the modulus is a frequent source of wrong answers.

4. Forgetting to divide by the shared factor in non-coprime systems

When moduli share a common factor, a congruence like 4k ≡ 4 (mod 6) must be divided through by gcd(4, 6) = 2 to become 2k ≡ 2 (mod 3) before you can find an inverse — 4 has no inverse mod 6 at all, since gcd(4, 6) ≠ 1.

5. Stopping before reducing the final sum modulo M

The weighted sum from Step 4 (for example, 233 in the Sunzi problem) is not the final answer — it must be reduced modulo M (233 mod 105 = 23) to reach the smallest nonnegative solution.

If your answer doesn't satisfy every original congruence when you plug it back in, recheck the compatibility test and the modular inverses first — that's where nearly every CRT mistake actually happens.

Practice Problems: Test Your Chinese Remainder Theorem Calculator Skills

Work through these three systems by hand, checking pairwise coprimality or compatibility first, before comparing against the solutions below. The second problem is deliberately unsolvable — recognizing that is as important as finding a numeric answer when it exists.

1. Problem 1 (pairwise coprime)

Solve: x ≡ 1 (mod 3), x ≡ 4 (mod 5), x ≡ 6 (mod 7). Answer: M = 105. M₁ = 35 with inverse 2 mod 3; M₂ = 21 with inverse 1 mod 5; M₃ = 15 with inverse 1 mod 7. Sum = (1×35×2) + (4×21×1) + (6×15×1) = 70 + 84 + 90 = 244. 244 mod 105 = 34. Check: 34 mod 3 = 1 ✓, 34 mod 5 = 4 ✓, 34 mod 7 = 6 ✓. Solution: x ≡ 34 (mod 105).

2. Problem 2 (incompatible moduli — no solution)

Solve: x ≡ 2 (mod 8), x ≡ 5 (mod 12). gcd(8, 12) = 4. Reduce: 2 mod 4 = 2, and 5 mod 4 = 1. Since 2 ≠ 1, the system is incompatible and has no solution — a Chinese remainder theorem calculator should return this conclusion rather than an incorrect number.

3. Problem 3 (compatible non-coprime moduli)

Solve: x ≡ 5 (mod 9), x ≡ 2 (mod 6). gcd(9, 6) = 3. Reduce: 5 mod 3 = 2, and 2 mod 3 = 2 — compatible. lcm(9, 6) = 18. Write x = 9k + 5, substitute: 9k + 5 ≡ 2 (mod 6) → 9k ≡ −3 ≡ 3 (mod 6). Divide by gcd(9, 6) = 3: 3k ≡ 1 (mod 2) → k ≡ 1 (mod 2). So k = 2j + 1, giving x = 9(2j+1) + 5 = 18j + 14. Check: 14 mod 9 = 5 ✓, 14 mod 6 = 2 ✓. Solution: x ≡ 14 (mod 18). If you want to double-check every modular inverse and reduction step on a problem like this, Solvify's step-by-step math solver will walk through each stage the same way this guide does.

The fastest way to build real fluency with the Chinese Remainder Theorem is to solve a mix of coprime, non-coprime-but-compatible, and incompatible systems — recognizing which case you're in is half the skill.

태그: