Solve systems of 2 or 3 congruences with the Chinese Remainder Theorem. Normalize residues, merge non-coprime systems, verify every modulus, and list the full solution family.
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.
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 error-prone 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 for you 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.
For a pair of congruences x congruent to a (mod m) and x congruent to b (mod n), let g = gcd(m, n). A solution exists only if a - b is divisible by g. When it is, write m = g*m1 and n = g*n1, solve m1*t congruent to (b - a)/g (mod n1), then combine to x congruent to a + m*t (mod lcm(m, n)). In the pairwise-coprime case, this reduces to the classic CRT construction with modular inverses.
Result: x congruent to 23 (mod 105)
The smallest non-negative solution is 23 because 23 mod 3 = 2, 23 mod 5 = 3, and 23 mod 7 = 2. Since 3, 5, and 7 are pairwise coprime, the combined modulus is their product 105, so every solution has the form x = 23 + 105k.
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.
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.
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.
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.
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.
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.
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.
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.
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. Use this as a practical reminder before finalizing the result.