Chinese Remainder Theorem
Chinese Remainder Theorem Solver solves a system of congruences \\( x \equiv a_i \pmod{m_i} \\) for pairwise coprime moduli and plots the solution space.
Chinese Remainder Theorem
The Chinese Remainder Theorem states that if the moduli \\( m_1, m_2, \ldots, m_k \\) are pairwise coprime, then the system of congruences:
has a unique solution modulo \\( M = m_1 \cdot m_2 \cdot \ldots \cdot m_k \\).
Solution Method:
- Compute \\( M = m_1 \cdot m_2 \cdot \ldots \cdot m_k \\).
- For each \\( i \\), compute \\( M_i = M / m_i \\) and find the modular inverse \\( y_i \\) such that \\( M_i \cdot y_i \equiv 1 \pmod{m_i} \\).
- The solution is: \\[ x = \sum_{i=1}^k a_i \cdot M_i \cdot y_i \pmod{M} \\]
- General solution: \\( x + k \cdot M \\), where \\( k \in \mathbb{Z} \\).
Examples
Example 1
System: \\( x \equiv 2 \pmod{3}, x \equiv 3 \pmod{4}, x \equiv 4 \pmod{5} \\)
Moduli: \\( 3, 4, 5 \\) (pairwise coprime).
\\( M = 3 \cdot 4 \cdot 5 = 60 \\).
\\( M_1 = 60/3 = 20 \\), \\( M_2 = 60/4 = 15 \\), \\( M_3 = 60/5 = 12 \\).
Inverses: \\( 20 \cdot 2 \equiv 1 \pmod{3} \\), \\( 15 \cdot 3 \equiv 1 \pmod{4} \\), \\( 12 \cdot 3 \equiv 1 \pmod{5} \\).
Solution: \\( x = 2 \cdot 20 \cdot 2 + 3 \cdot 15 \cdot 3 + 4 \cdot 12 \cdot 3 = 80 + 135 + 144 = 359 \equiv 59 \pmod{60} \\).
Example 2
System: \\( x \equiv 1 \pmod{5}, x \equiv 2 \pmod{7} \\)
Moduli: \\( 5, 7 \\) (pairwise coprime).
\\( M = 5 \cdot 7 = 35 \\).
\\( M_1 = 35/5 = 7 \\), \\( M_2 = 35/7 = 5 \\).
Inverses: \\( 7 \cdot 3 \equiv 1 \pmod{5} \\), \\( 5 \cdot 3 \equiv 1 \pmod{7} \\).
Solution: \\( x = 1 \cdot 7 \cdot 3 + 2 \cdot 5 \cdot 3 = 21 + 30 = 51 \equiv 16 \pmod{35} \\).
Example 3
System: \\( x \equiv 3 \pmod{4}, x \equiv 4 \pmod{9} \\)
Moduli: \\( 4, 9 \\) (not coprime, \\( \gcd(4, 9) = 1 \\), but we proceed).
\\( M = 4 \cdot 9 = 36 \\).
\\( M_1 = 36/4 = 9 \\), \\( M_2 = 36/9 = 4 \\).
Inverses: \\( 9 \cdot 1 \equiv 1 \pmod{4} \\), \\( 4 \cdot 7 \equiv 1 \pmod{9} \\).
Solution: \\( x = 3 \cdot 9 \cdot 1 + 4 \cdot 4 \cdot 7 = 27 + 112 = 139 \equiv 31 \pmod{36} \\).