Chinese Remainder Theorem Calculator
This calculator solves systems of simultaneous congruences using the Chinese Remainder Theorem (CRT). It is useful for students and professionals in number theory, cryptography, and modular arithmetic applications.
Chinese Remainder Theorem Solver
Formula of the Chinese Remainder Theorem Calculator
\[
x \equiv a_1 \pmod{m_1} \\
x \equiv a_2 \pmod{m_2} \\
\vdots \\
x \equiv a_k \pmod{m_k} \\[1.5em]
M = m_1 \cdot m_2 \cdots m_k \\
M_i = \frac{M}{m_i}, \quad y_i \equiv M_i^{-1} \pmod{m_i} \\[1.5em]
x \equiv \sum_{i=1}^{k} a_i \cdot M_i \cdot y_i \pmod{M}
\]
Where:
- $$a_i$$ are the remainders
- $$m_i$$ are pairwise coprime moduli
- $$M$$ is the product of all $$m_i$$
- $$M_i$$ is $$M$$ divided by $$m_i$$
- $$y_i$$ is the modular inverse of $$M_i \mod m_i$$
- $$x$$ is the unique solution modulo $$M$$
Chinese Remainder Theorem – Calculation Example
Given:
- \( x \equiv 2 \mod 3 \)
- \( x \equiv 3 \mod 5 \)
- \( x \equiv 2 \mod 7 \)
Steps:
- $$M = 3 \times 5 \times 7 = 105$$
- $$M_1 = \frac{105}{3} = 35 \quad\Rightarrow\quad y_1 = 2 \quad (\text{since } 35 \cdot 2 \equiv 1 \mod 3)$$
- $$M_2 = \frac{105}{5} = 21 \quad\Rightarrow\quad y_2 = 1 \quad (\text{since } 21 \cdot 1 \equiv 1 \mod 5)$$
- $$M_3 = \frac{105}{7} = 15 \quad\Rightarrow\quad y_3 = 1 \quad (\text{since } 15 \cdot 1 \equiv 1 \mod 7)$$
- $$x \equiv (2 \cdot 35 \cdot 2 + 3 \cdot 21 \cdot 1 + 2 \cdot 15 \cdot 1) \mod 105$$
- $$x \equiv (140 + 63 + 30) \mod 105 = 233 \mod 105 = 23$$
\( \boxed{x \equiv 23 \mod{105}} \)
The Chinese Remainder Theorem provides a method for solving systems of modular equations with pairwise coprime moduli. It has applications in cryptography (RSA, Shamir’s secret sharing), computer algebra systems, and algorithm optimization. This calculator automates the full solution using modular inverses.