Home › Math & Conversions › Core Math & Algebra › Chinese Remainder Theorem Calculator Chinese Remainder Theorem Calculator Solve systems of congruences of the form \(x \equiv a_i \pmod{m_i}\). The tool checks consistency, handles non-coprime moduli, and shows a least nonnegative solution when it exists. Designed for number theory, cryptography, and contest training where a transparent, step-by-step CRT solver is more useful than a black box. CRT system solver Generalized Chinese remainder theorem Enter your congruences \(x \equiv a_i \pmod{m_i}\) and click Calculate . The solver uses the extended Euclidean algorithm, detects incompatibilities, and reports the solution modulo the combined modulus. Number of congruences Between 2 and 8 rows. Empty rows are ignored. Update table Load classic example Example: \(x \equiv 2 \pmod{3}\), \(x \equiv 3 \pmod{5}\), \(x \equiv 2 \pmod{7}\). Notes: Moduli \(m_i\) must be positive integers. The solver uses arbitrary-precision integers (BigInt) for robustness. Calculate Clear Backend: extended Euclidean algorithm and iterative CRT merging. Solution, combined modulus, and step-by-step CRT construction will appear here after you click Calculate . Chinese remainder theorem – definition and intuition The Chinese remainder theorem (CRT) describes when a system of congruences \[ x \equiv a_1 \pmod{m_1},\quad x \equiv a_2 \pmod{m_2},\quad \dots,\quad x \equiv a_k \pmod{m_k} \] has a solution, and how to describe all such solutions. Informally: if the congruences are mutually compatible, there is a unique solution modulo the least common multiple of the moduli. Classical CRT with pairwise coprime moduli In the classical setting, the moduli \(m_1,\dots,m_k\) are pairwise coprime \((\gcd(m_i,m_j) = 1\) for \(i \neq j)\). Let \(M = m_1 m_2 \cdots m_k\) and \[ M_i = \frac{M}{m_i},\qquad N_i \equiv M_i^{-1} \pmod{m_i}, \] where \(M_i^{-1}\) denotes the modular inverse of \(M_i\) modulo \(m_i\). Then one explicit solution is \[ x_0 \equiv \sum_{i=1}^k a_i M_i N_i \pmod{M}. \] Every solution is congruent to \(x_0\) modulo \(M\), so the full solution set is \(x = x_0 + tM\) for \(t \in \mathbb{Z}\). Generalized CRT with non-coprime moduli When the moduli are not pairwise coprime, the situation is more subtle. For two congruences \[ x \equiv a_1 \pmod{m_1},\qquad x \equiv a_2 \pmod{m_2}, \] a solution exists if and only if \(\;a_1 \equiv a_2 \pmod{\gcd(m_1, m_2)}\). If this compatibility condition holds, the two congruences have a common solution, and the combined modulus is \(\operatorname{lcm}(m_1, m_2)\). The calculator implements this generalized CRT by merging congruences one pair at a time, always checking the relevant gcd condition. If any pair is incompatible, it reports that the system has no solution. Algorithm used by the calculator Let \(x \equiv a \pmod{n}\) describe the current combined congruence, and suppose we want to merge \(x \equiv b \pmod{m}\). Compute \(g = \gcd(n, m)\). If \(a \not\equiv b \pmod{g}\), the system is inconsistent and has no solution. Otherwise set \(n_1 = n/g\), \(m_1 = m/g\), and \(r = (b - a)/g\). Find the modular inverse of \(n_1\) modulo \(m_1\) using the extended Euclidean algorithm. Compute \(t \equiv r \cdot n_1^{-1} \pmod{m_1}\) and set \(x = a + n t\), \(N = n \cdot m_1\). After processing every congruence, we end up with a single congruence \(x \equiv x_0 \pmod{N}\) that encodes all solutions, where \(N\) is the least common multiple of the original moduli. Applications: from calendars to cryptography The Chinese remainder theorem appears in many contexts: calendar calculations and periodic scheduling, coding theory and cryptographic schemes such as RSA, modular arithmetic with large integers via residue systems, programming contests and algorithmic number theory. In each case, CRT allows a large modular problem to be broken into smaller, independent pieces that are easier to work with and then recombined in a mathematically sound way. Chinese remainder theorem – FAQ What happens if some moduli share a common factor? + The calculator does not require the moduli to be pairwise coprime. If two moduli share a non-trivial gcd, it checks whether the corresponding remainders agree modulo that gcd. If they do, the congruences can still be merged; otherwise, the system has no solution and the conflicting pair is reported explicitly. Why is the solution unique modulo the combined modulus? + Once a solution x₀ exists, any other integer x that satisfies all congruences must differ from x₀ by a multiple of every modulus, hence by a multiple of their least common multiple M. Conversely, x₀ + kM satisfies each congruence for every integer k, so the solution set is exactly one residue class modulo M. Can I use this tool for cryptographic-size numbers? + The implementation uses JavaScript BigInt, which supports very large integers. However, browsers are not optimized for extremely heavy big-integer workloads. For production cryptographic deployments you should rely on vetted, specialized libraries and carefully audited code rather than a general-purpose web calculator. Core Math & Algebra tools Modular Arithmetic Equation Solver Circular Segment Area Trig Identity Explorer Hyperbolic Function Explorer Linear Algebra Toolbox Trapezoidal Rule Calculator Perfect Number Calculator Chinese Remainder Theorem (you are here) Set Theory Basics Number theory & discrete math Base Converter Interval Notation Helper Pythagorean Theorem Convolution Explorer Dice Roll Probability Professional use note This CRT calculator is ideal for teaching, exam preparation, and prototyping of modular arithmetic schemes. For production cryptography or safety-critical applications, validate all logic with independent implementations and domain-specific tooling.

Subcategories in Home › Math & Conversions › Core Math & Algebra › Chinese Remainder Theorem Calculator Chinese Remainder Theorem Calculator Solve systems of congruences of the form \(x \equiv a_i \pmod{m_i}\). The tool checks consistency, handles non-coprime moduli, and shows a least nonnegative solution when it exists. Designed for number theory, cryptography, and contest training where a transparent, step-by-step CRT solver is more useful than a black box. CRT system solver Generalized Chinese remainder theorem Enter your congruences \(x \equiv a_i \pmod{m_i}\) and click Calculate . The solver uses the extended Euclidean algorithm, detects incompatibilities, and reports the solution modulo the combined modulus. Number of congruences Between 2 and 8 rows. Empty rows are ignored. Update table Load classic example Example: \(x \equiv 2 \pmod{3}\), \(x \equiv 3 \pmod{5}\), \(x \equiv 2 \pmod{7}\). Notes: Moduli \(m_i\) must be positive integers. The solver uses arbitrary-precision integers (BigInt) for robustness. Calculate Clear Backend: extended Euclidean algorithm and iterative CRT merging. Solution, combined modulus, and step-by-step CRT construction will appear here after you click Calculate . Chinese remainder theorem – definition and intuition The Chinese remainder theorem (CRT) describes when a system of congruences \[ x \equiv a_1 \pmod{m_1},\quad x \equiv a_2 \pmod{m_2},\quad \dots,\quad x \equiv a_k \pmod{m_k} \] has a solution, and how to describe all such solutions. Informally: if the congruences are mutually compatible, there is a unique solution modulo the least common multiple of the moduli. Classical CRT with pairwise coprime moduli In the classical setting, the moduli \(m_1,\dots,m_k\) are pairwise coprime \((\gcd(m_i,m_j) = 1\) for \(i \neq j)\). Let \(M = m_1 m_2 \cdots m_k\) and \[ M_i = \frac{M}{m_i},\qquad N_i \equiv M_i^{-1} \pmod{m_i}, \] where \(M_i^{-1}\) denotes the modular inverse of \(M_i\) modulo \(m_i\). Then one explicit solution is \[ x_0 \equiv \sum_{i=1}^k a_i M_i N_i \pmod{M}. \] Every solution is congruent to \(x_0\) modulo \(M\), so the full solution set is \(x = x_0 + tM\) for \(t \in \mathbb{Z}\). Generalized CRT with non-coprime moduli When the moduli are not pairwise coprime, the situation is more subtle. For two congruences \[ x \equiv a_1 \pmod{m_1},\qquad x \equiv a_2 \pmod{m_2}, \] a solution exists if and only if \(\;a_1 \equiv a_2 \pmod{\gcd(m_1, m_2)}\). If this compatibility condition holds, the two congruences have a common solution, and the combined modulus is \(\operatorname{lcm}(m_1, m_2)\). The calculator implements this generalized CRT by merging congruences one pair at a time, always checking the relevant gcd condition. If any pair is incompatible, it reports that the system has no solution. Algorithm used by the calculator Let \(x \equiv a \pmod{n}\) describe the current combined congruence, and suppose we want to merge \(x \equiv b \pmod{m}\). Compute \(g = \gcd(n, m)\). If \(a \not\equiv b \pmod{g}\), the system is inconsistent and has no solution. Otherwise set \(n_1 = n/g\), \(m_1 = m/g\), and \(r = (b - a)/g\). Find the modular inverse of \(n_1\) modulo \(m_1\) using the extended Euclidean algorithm. Compute \(t \equiv r \cdot n_1^{-1} \pmod{m_1}\) and set \(x = a + n t\), \(N = n \cdot m_1\). After processing every congruence, we end up with a single congruence \(x \equiv x_0 \pmod{N}\) that encodes all solutions, where \(N\) is the least common multiple of the original moduli. Applications: from calendars to cryptography The Chinese remainder theorem appears in many contexts: calendar calculations and periodic scheduling, coding theory and cryptographic schemes such as RSA, modular arithmetic with large integers via residue systems, programming contests and algorithmic number theory. In each case, CRT allows a large modular problem to be broken into smaller, independent pieces that are easier to work with and then recombined in a mathematically sound way. Chinese remainder theorem – FAQ What happens if some moduli share a common factor? + The calculator does not require the moduli to be pairwise coprime. If two moduli share a non-trivial gcd, it checks whether the corresponding remainders agree modulo that gcd. If they do, the congruences can still be merged; otherwise, the system has no solution and the conflicting pair is reported explicitly. Why is the solution unique modulo the combined modulus? + Once a solution x₀ exists, any other integer x that satisfies all congruences must differ from x₀ by a multiple of every modulus, hence by a multiple of their least common multiple M. Conversely, x₀ + kM satisfies each congruence for every integer k, so the solution set is exactly one residue class modulo M. Can I use this tool for cryptographic-size numbers? + The implementation uses JavaScript BigInt, which supports very large integers. However, browsers are not optimized for extremely heavy big-integer workloads. For production cryptographic deployments you should rely on vetted, specialized libraries and carefully audited code rather than a general-purpose web calculator. Core Math & Algebra tools Modular Arithmetic Equation Solver Circular Segment Area Trig Identity Explorer Hyperbolic Function Explorer Linear Algebra Toolbox Trapezoidal Rule Calculator Perfect Number Calculator Chinese Remainder Theorem (you are here) Set Theory Basics Number theory & discrete math Base Converter Interval Notation Helper Pythagorean Theorem Convolution Explorer Dice Roll Probability Professional use note This CRT calculator is ideal for teaching, exam preparation, and prototyping of modular arithmetic schemes. For production cryptography or safety-critical applications, validate all logic with independent implementations and domain-specific tooling..