Enter a system of congruences — each with a remainder (a) and a modulus (m) — and the Chinese Remainder Theorem Calculator finds the unique solution x satisfying all equations simultaneously. Choose between 2 to 6 equations, fill in your values, and get the smallest non-negative solution along with the combined modulus.
Solution x
--
Combined Modulus M
--
Solution Status
--
General Solution (x + k·M)
--
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 (share no common factors), then there exists a unique solution x modulo the product M = m₁ × m₂ × ... × mₙ. It was first described by the ancient Chinese mathematician Sun Tzu and has wide applications in cryptography, computer science, and number theory.
Two numbers are coprime if their greatest common divisor (GCD) equals 1. Pairwise coprime means every pair of moduli in your system satisfies this condition. The CRT requires this property to guarantee a unique solution exists. If two moduli share a common factor, the system may have no solution or infinitely many solutions that can't be reduced to a single residue.
A congruence x ≡ a (mod m) means that x and a leave the same remainder when divided by m, or equivalently, m divides (x − a). For example, x ≡ 2 (mod 3) is satisfied by x = 2, 5, 8, 11, and so on — any number that gives remainder 2 when divided by 3.
The algorithm computes M = m₁ × m₂ × ... × mₙ (the product of all moduli), then for each equation finds Mᵢ = M / mᵢ and the modular inverse of Mᵢ modulo mᵢ using the extended Euclidean algorithm. The solution is x = Σ(aᵢ × Mᵢ × inverse(Mᵢ)) mod M. This gives the smallest non-negative solution.
The modular inverse of a number n modulo m is a value y such that n × y ≡ 1 (mod m). It is found using the extended Euclidean algorithm, which is based on Bézout's identity: for coprime integers a and b, there exist integers x and y such that a·x + b·y = 1. The coefficient x in this identity gives the modular inverse of a modulo b.
The Euclidean algorithm is a method for finding the GCD of two numbers through repeated division: gcd(a, b) = gcd(b, a mod b) until the remainder is 0. The extended version also tracks back-substitution to express the GCD as a linear combination of the two numbers. This is essential for computing modular inverses required by the CRT algorithm.
When moduli are not pairwise coprime, the standard CRT does not directly apply. This calculator detects such cases and reports if no unique solution exists. A generalized version of CRT can sometimes still find solutions when moduli share common factors, but only if the remainders also satisfy specific compatibility conditions.
The CRT has important applications in RSA cryptography (speeding up private key operations), computer arithmetic (working with large numbers by splitting them into smaller modular pieces), coding theory (error detection and correction), and scheduling problems (finding dates or times that satisfy multiple cyclic constraints simultaneously).