What is the Chinese Remainder Theorem?

It states that if you know the remainders of an unknown integer x when divided by several pairwise-coprime numbers, you can uniquely determine x modulo the product of those numbers.

Why must the moduli be pairwise coprime?

The theorem's guarantee of a unique solution modulo the product only holds when every pair of moduli shares no common factor. If two moduli share a factor, either no solution exists or the system is redundant, and standard CRT construction doesn't apply.

How is the solution constructed?

For each congruence x ≡ aᵢ (mod mᵢ), the algorithm computes Mᵢ = M/mᵢ (where M is the product of all moduli) and its modular inverse yᵢ mod mᵢ, then sums aᵢ×Mᵢ×yᵢ over all congruences and reduces modulo M.

What does the answer 'x ≡ r (mod M)' mean?

It means every integer of the form r + k×M (for any integer k) satisfies all the original congruences simultaneously — r is simply the smallest non-negative representative of that solution set.

How many congruences can I enter?

This calculator supports 2 to 10 simultaneous congruences, which covers the overwhelming majority of practical CRT problems.

What's the classic 'three baskets' style example this solves?

The classic puzzle 'find a number that leaves remainder 2 divided by 3, remainder 3 divided by 5, and remainder 2 divided by 7' is exactly a 3-congruence CRT system, solvable directly with this calculator.

Where is CRT used in real life?

It underlies fast RSA decryption (CRT-RSA), computer arithmetic using residue number systems, calendar and scheduling calculations, and error-correcting codes.

What happens if a modulus is not coprime with another?

The calculator detects the shared factor and reports exactly which pair of moduli conflict, rather than returning an incorrect or incomplete solution.

Chinese Remainder Theorem Calculator — Solve a System of Congruences

Our Chinese Remainder Theorem Calculator solves systems of simultaneous congruences — x ≡ a₁ (mod m₁), x ≡ a₂ (mod m₂), and so on — finding the unique solution modulo the product of the moduli, provided the moduli are pairwise coprime. It validates coprimality up front and computes the solution with BigInt precision.

Quick Answer

Enter each congruence as remainder,modulus (one per line, at least two lines) to instantly solve the system for x via the Chinese Remainder Theorem's constructive method.

Congruences (remainder,modulus per line)

Enter at least two congruences, one per line, e.g. 2,3 for x ≡ 2 (mod 3). Moduli must be pairwise coprime.

How to Use the Chinese Remainder Theorem Calculator — Solve Modular Systems

1
Enter each congruence as "remainder,modulus" on its own line — at least two lines.
2
Click 'Calculate' to solve the system for x.
3
Review the combined modulus and the step-by-step construction of the solution.

Why Use Chinese Remainder Theorem Calculator — Solve Modular Systems?

The Chinese Remainder Theorem, first recorded by the Chinese mathematician Sun Tzu around the 3rd century AD, guarantees that a system of congruences with pairwise-coprime moduli has a unique solution modulo the product of those moduli — and gives an explicit constructive method to find it. This calculator validates that your moduli are actually pairwise coprime (the theorem's precondition) before combining the congruences via the standard construction, using each modulus's partial product and modular inverse.

Frequently Asked Questions

Related Tools

Extended Euclidean Algorithm Calculator — gcd + Bézout Coefficients

Compute gcd(a, b) and the Bézout coefficients x, y satisfying ax + by = gcd(a, b) using the extended Euclidean algorithm. Free calculator with BigInt precision.

Modular Multiplicative Inverse Calculator — Solve ax ≡ 1 (mod m)

Find the modular multiplicative inverse of a modulo m using the extended Euclidean algorithm. Free calculator with BigInt precision and existence check.

Primitive Root Calculator — Find a Generator mod n

Find the smallest primitive root modulo n — a generator of the multiplicative group mod n — with existence checking via Euler's totient function. Free calculator.