Chinese Remainder Calculator

About the Chinese Remainder Calculator

The Chinese Remainder Theorem is the standard tool for solving simultaneous congruences such as x congruent to 2 mod 3, x congruent to 3 mod 5, and x congruent to 2 mod 7. Instead of testing values one by one, CRT combines the separate modular conditions into a single residue class x congruent to r mod M. That final statement describes every solution at once, which is exactly what makes CRT so valuable in number theory, cryptography, scheduling cycles, coding theory, and contest math.

This calculator handles both the textbook CRT case with pairwise-coprime moduli and the more useful real-world case where moduli can share factors. It first normalizes every remainder into the standard range 0 through n-1, then merges the congruences one by one using the extended Euclidean algorithm. If the system is compatible, you get the smallest non-negative solution, the combined modulus, and a list of subsequent solutions. If the system is inconsistent, the calculator shows exactly where the merge fails and why the residue difference breaks compatibility.

The extra detail matters. Students can inspect each merge step instead of memorizing a black-box rule, while engineers and programmers can confirm that a modular system is valid before plugging it into downstream logic. The residue map, verification table, and solution-family list make the result immediately usable for both learning and applied work.

When This Page Helps

Solving a congruence system by hand usually means juggling products of moduli, modular inverses, gcd checks, and normalization rules all at once. That is manageable for one homework example, but it becomes fragile as soon as one modulus is negative, one remainder lies outside the standard range, or two moduli are not coprime. This calculator does the bookkeeping while still exposing the arithmetic: normalized congruences, gcd compatibility checks, merge multipliers, and the final residue class. It is especially useful for validating programming answers, checking cryptography exercises, and demonstrating how generalized CRT works when the moduli share factors.

How to Use the Inputs

1. Choose whether your system has 2 or 3 congruences.
2. Enter each remainder ai and modulus ni. Moduli must be integers greater than 1.
3. Use a preset if you want to test a classic CRT example, a non-coprime solvable system, or an incompatible system.
4. Set how many solution rows you want to list after the smallest solution is found.
5. Read the output cards for the smallest solution, combined modulus, and solution family.
6. Check the normalized congruence table to see every remainder converted into standard modular form.
7. Review the merge-steps table to understand the gcd checks, multiplier, and merged modulus at each stage.
8. Use the residue map and solution-family table to verify that every listed solution satisfies every original congruence.

Example Calculation

Tips & Best Practices

• Always normalize remainders first. A statement like x congruent to -1 mod 7 is easier to work with as x congruent to 6 mod 7.
• If two moduli share a gcd greater than 1, do not assume the system fails. It only fails when the residue difference is not divisible by that gcd.
• In the pairwise-coprime case, the final modulus is simply the product of all moduli.
• If you only need one representative solution, use the smallest non-negative one. If you need every solution, keep the full residue-class form x = r + kM.
• CRT is often easier to verify than to derive. Plug the final x back into each modulus check before moving on.
• For programming contests and cryptography tasks, keep track of overflow when multiplying large moduli. The math may be simple even when the integers are not.

Why Generalized CRT Matters

Textbook treatments often present CRT only for pairwise-coprime moduli because the formulas are clean. Real problems are messier. Shared factors show up in clock arithmetic, packet scheduling, and programmatic constraint systems. In that broader setting, the important question is not just whether the moduli are coprime, but whether the congruences are compatible. That is why this calculator exposes the gcd and residue-difference check at each merge step.

Reading The Solution Family

Once the system is merged, the result x congruent to r mod M is stronger than a single numeric answer. It tells you the smallest solution r, the spacing M between every subsequent solution, and the exact structure of the entire set. That is useful when you need the first solution above a threshold, the next event in a repeating system, or a quick way to generate test cases.

CRT And Modular Inverses

The engine underneath CRT is the modular inverse, usually found with the extended Euclidean algorithm. When two reduced moduli are coprime, the inverse lets you solve for the multiplier that aligns one residue class with another. Understanding that link is valuable because the same inverse computation powers modular division, linear congruence solving, and many cryptographic routines.

Frequently Asked Questions

• What does the Chinese Remainder Theorem actually solve?

  It solves systems of simultaneous modular equations. Instead of finding one x for one modulus, CRT finds the residue class of all x values that satisfy several congruence conditions at once.

• Do the moduli have to be pairwise coprime?

  No. Pairwise coprime moduli guarantee a unique solution modulo the product, but generalized CRT also handles shared factors. The key condition is compatibility: each residue difference must be divisible by the gcd of the relevant moduli during merging.

• Why does the calculator normalize negative remainders?

  Because modular arithmetic works with residue classes, not one specific representative. Writing -1 mod 7 as 6 mod 7 keeps every remainder in the standard range and makes checks, tables, and modular inverses easier to interpret.

• What does x congruent to 23 mod 105 mean?

  It means every solution differs from 23 by a multiple of 105. So 23, 128, 233, and 338 are all valid solutions, and there are no others outside that residue class.

• Why can a system fail even when each congruence looks valid by itself?

  Because two congruences can demand incompatible residues on overlapping modular cycles. For example, x congruent to 1 mod 4 and x congruent to 2 mod 6 conflict because their residue difference is not divisible by gcd(4, 6) = 2.

• Where is CRT used outside the classroom?

  It appears in RSA implementations, hash-table design, calendar-cycle problems, parallel arithmetic, coding theory, and any system that combines repeated cycles or modular constraints into one synchronized schedule.