Statement of the Chinese Remainder Theorem

The Chinese remainder theorem states that a system of simultaneous congruences has a unique solution modulo the product of pairwise coprime moduli. In symbolic form, given $x$ satisfying $x\equiv r_{\mathrm{i}}\left(m_{\mathrm{i}}\right)$ for $i$ from $1$ to $k$, there exists an integer $x$ modulo ${\prod }_i^1{m}_i$ solving all equations if the moduli are mutually coprime. This theorem, originating from ancient Chinese mathematics, is a fundamental result in number theory with applications in cryptography and coding theory.

Why It Matters

In practical terms, the theorem allows us to reconstruct an unknown number from its remainders upon division by several pairwise coprime numbers. This is useful for computer arithmetic, where numbers are often handled in modular segments. The RSA cryptosystem leverages the Chinese remainder theorem to speed up exponentiation, while error-correcting codes use it to reconstruct messages from fragments. The theorem also illustrates the deep structure of the integers and modular arithmetic.

Solving the System

The typical approach is to compute each modulus product $M=m_1{m}_2\backslash ldots{m}_k$. For each equation, we define $M_{\mathrm{i}}=\frac{M}{m_i}$ and compute its modular inverse $N_{\mathrm{i}}=M_{\mathrm{i}}{\mathrm{-1}}^{}\left(m_i\right)$. The final solution is then $x={\sum }_i{r}_i{M}_i{N}_i\left(\mathrm{mod}M\right)$. This calculator implements precisely that algorithm.

Using the Calculator

Enter up to three congruences of the form $x\equiv r_i\left(m_i\right)$. All moduli must be positive integers, and each pair should be coprime for a unique solution to exist. If you enter only two congruences, leave the third pair blank. After clicking Solve, the calculator computes $x$ and displays both the solution and the modulus $M$. If the moduli are not coprime, the tool alerts you that a unique solution does not exist.

Example Problem

Suppose we wish to find $x$ such that $x\equiv 2\left(3\right)$, $x\equiv 3\left(5\right)$, and $x\equiv 2\left(7\right)$. The moduli 3, 5, and 7 are pairwise coprime. Their product is $105$. Following the procedure above, we obtain $x=23$ modulo 105. Verifying, we see that 23 leaves remainders 2, 3, and 2 upon division by 3, 5, and 7 respectively. The calculator reproduces this solution automatically.

Historical Origins

The theorem traces back to the 3rd century Chinese text "Sunzi Suanjing." It was later formalized and extended by mathematicians such as Qin Jiushao in the 13th century and Carl Friedrich Gauss in the 19th. Its longevity arises from its simple but profound observation about congruences. By piecing together local remainders, one reconstructs a global number—a concept that underlies modern algebraic structures like rings and fields.

Applications in Modern Computing

Beyond theoretical interest, the Chinese remainder theorem underpins efficient modular arithmetic. In cryptography, breaking large calculations into smaller moduli speeds up exponentiation and improves hardware efficiency. For digital signal processing and coding theory, the theorem aids in reconstructing signals from sampled residues. It also appears in algorithmic number theory, where it helps find solutions to polynomial congruences or compute integer factorizations.

Checking Coprimality

To apply the Chinese remainder theorem properly, the moduli must be pairwise coprime. This calculator checks by computing the greatest common divisor of each pair. If any pair shares a factor larger than one, the theorem does not guarantee a unique solution. In such cases, a solution may still exist, but additional reasoning or algorithms are required. Ensuring coprime moduli simplifies the system and yields a clear result.

Further Exploration

Once you master solving small systems with this calculator, you can explore generalizations. For larger sets of congruences, the algorithm scales naturally by iterating the product and inverse calculations. In abstract algebra, the theorem extends to ring theory, showing that the ring of integers modulo $M$ is isomorphic to the direct product of the smaller modulus rings. This perspective illuminates how seemingly separate congruence classes combine to form a cohesive structure.

Whether you are studying number theory for fun or applying modular arithmetic in computer science, understanding the Chinese remainder theorem is immensely valuable. This calculator aims to make the process tangible so you can experiment with your own sets of congruences and see how the solution emerges.