Chinese Remainder Theorem Solver

Enter up to 5 simultaneous congruences — each with a remainder (a) and a modulus (m) — and the Chinese Remainder Theorem Solver finds the unique solution x satisfying all equations at once. Optionally include a coefficient (b) for equations of the form bx ≡ a (mod m). The solver returns the smallest non-negative solution and the combined modulus M, so you can verify and extend the result yourself.

How many simultaneous congruences to solve

x ≡ a₁ (mod m₁)

Must be a positive integer ≥ 2

x ≡ a₂ (mod m₂)

Must be a positive integer ≥ 2

x ≡ a₃ (mod m₃)

Must be a positive integer ≥ 2

Results

Solution x (smallest non-negative)

--

Combined Modulus M

--

Solution Status

--

General Solution (x + k·M)

--

Remainders by Modulus

Results Table

Frequently Asked Questions

What is the Chinese Remainder Theorem?

The Chinese Remainder Theorem (CRT) states that if you have a system of congruences x ≡ a₁ (mod m₁), x ≡ a₂ (mod m₂), … where all moduli are pairwise coprime (their GCDs are all 1), then there exists a unique solution modulo M = m₁ × m₂ × … × mₙ. It originated in ancient Chinese mathematics and has wide applications in cryptography, computer science, and number theory.

How do you calculate the Chinese Remainder Theorem solution?

For each equation, compute Mᵢ = M / mᵢ (the product of all other moduli). Then find the modular inverse yᵢ of Mᵢ mod mᵢ using the Extended Euclidean Algorithm. The solution is x = (Σ aᵢ · Mᵢ · yᵢ) mod M. This solver performs all these steps automatically and returns the smallest non-negative x.

When does the Chinese Remainder Theorem have no solution?

The standard CRT requires all moduli to be pairwise coprime — meaning GCD(mᵢ, mⱼ) = 1 for every pair i ≠ j. If any two moduli share a common factor greater than 1, the system may have no solution or infinitely many solutions modulo a smaller number. This solver checks for pairwise coprimality and will indicate if no unique solution exists.

What does the combined modulus M represent?

The combined modulus M is the product of all individual moduli: M = m₁ × m₂ × … × mₙ. The unique solution x found by the CRT is valid within the range [0, M−1]. Any integer of the form x + k·M (where k is any integer) is also a valid solution, which is why it's called a solution modulo M.

What is the Euclidean algorithm's role in the Chinese Remainder Theorem?

The Extended Euclidean Algorithm is used to compute the modular inverse of each Mᵢ modulo mᵢ. Specifically, it finds integers s and t such that Mᵢ·s + mᵢ·t = 1 (Bézout's identity), and s is the needed inverse. Without this step, the CRT construction cannot be completed.

Can the Chinese Remainder Theorem be applied to non-coprime moduli?

Yes, there is a generalization. For two congruences x ≡ a₁ (mod m₁) and x ≡ a₂ (mod m₂) with GCD(m₁, m₂) = d, a solution exists if and only if d divides (a₁ − a₂). If it does, the solution is unique modulo LCM(m₁, m₂). This solver focuses on the standard pairwise-coprime case for clarity.

What are practical applications of the Chinese Remainder Theorem?

The CRT is widely used in RSA cryptography to speed up decryption, in computer science for efficient large-integer arithmetic, in scheduling problems, and in error-correcting codes. Historically, it appeared in problems like 'find a number that leaves remainder 2 when divided by 3, remainder 3 when divided by 5, and remainder 2 when divided by 7' — classic puzzle-style problems that CRT solves definitively.

How many equations can this solver handle?

This solver supports systems of 2 to 5 simultaneous congruences. Select the number of equations from the dropdown, then enter the remainder (aᵢ) and modulus (mᵢ) for each. All moduli must be pairwise coprime for the standard CRT to apply, and each remainder must be less than its corresponding modulus.

More Math Tools