Chinese Remainder Theorem: Solve System of Congruences with Examples and Visuals

The Chinese Remainder Theorem (CRT) is a powerful tool in number theory and computer science for solving systems of simultaneous linear congruences with pairwise coprime moduli. It finds extensive applications in cryptography, computer algorithms, and coding theory. This article covers the theory behind CRT, detailed step-by-step methods to solve congruences, and concrete examples accompanied by insightful visualizations using mermaid diagrams.

Understanding the Chinese Remainder Theorem

The CRT states that if you have a system of congruences:

x ≡ a₁ (mod n₁)
x ≡ a₂ (mod n₂)
...
x ≡ aₖ (mod nₖ)

and the moduli \( n_1, n_2, …, n_k \) are pairwise coprime (meaning gcd between any two is 1), then there exists a unique solution modulo \( N = n_1 \times n_2 \times \cdots \times n_k \).

The CRT guarantees a single integer \( x \) such that \( x \equiv a_i \mod n_i \) for all i, with \( 0 \leq x < N \).

Step-by-Step Solution Method for CRT

1. Verify pairwise coprimality: Check gcd(n_i, n_j) = 1 for each i ≠ j.
2. Compute total modulus: \( N = \prod n_i \).
3. Calculate partial moduli: \( N_i = \frac{N}{n_i} \) for each i.
4. Find modular inverses: For each i, find \( M_i \) such that \( N_i \times M_i \equiv 1 \mod n_i \).
5. Build solution: \( x = \sum_{i=1}^k a_i \times M_i \times N_i \mod N \).
6. The result \( x \) is the unique solution modulo \( N \).

Example 1: Basic CRT Application

Solve the system:

x ≡ 2 (mod 3)
x ≡ 3 (mod 5)
x ≡ 2 (mod 7)

Step 1: Confirm moduli 3, 5, 7 are pairwise coprime.

Step 2: Calculate \( N = 3 \times 5 \times 7 = 105 \).

Step 3: Partial moduli:

• \( N_1 = 105 / 3 = 35 \)
• \( N_2 = 105 / 5 = 21 \)
• \( N_3 = 105 / 7 = 15 \)

Step 4: Find inverses:

• \( M_1 \) satisfies \( 35 \times M_1 \equiv 1 \mod 3 \Rightarrow 35 \equiv 2 \mod 3 \), so \( 2 \times M_1 \equiv 1 \mod 3 \), \( M_1 = 2 \)
• \( M_2 \) satisfies \( 21 \times M_2 \equiv 1 \mod 5 \Rightarrow 21 \equiv 1 \mod 5 \), so \( M_2 = 1 \)
• \( M_3 \) satisfies \( 15 \times M_3 \equiv 1 \mod 7 \Rightarrow 15 \equiv 1 \mod 7 \), so \( M_3 = 1 \)

Step 5: Compute solution:

\[
x = (2 \times 2 \times 35) + (3 \times 1 \times 21) + (2 \times 1 \times 15) = 140 + 63 + 30 = 233
\]

Step 6: Final result modulo \( N \):

\[
x \equiv 233 \mod 105 \equiv 23
\]

So, x = 23 is the unique solution modulo 105.

Example 2: Solving CRT Programmatically (Python Snippet)

Below is a simple Python function demonstrating the CRT solution approach for two congruences (extendable to more):

def egcd(a, b):
    if b == 0: return (a, 1, 0)
    g, x1, y1 = egcd(b, a % b)
    return (g, y1, x1 - (a // b) * y1)

def mod_inverse(a, m):
    g, x, _ = egcd(a, m)
    if g != 1:
        raise Exception('No modular inverse')
    return x % m

def chinese_remainder_theorem(a, n):
    assert len(a) == len(n)
    N = 1
    for ni in n: N *= ni

    result = 0
    for ai, ni in zip(a, n):
        Ni = N // ni
        Mi = mod_inverse(Ni, ni)
        result += ai * Mi * Ni
    return result % N

# Example usage
a = [2,3,2]
n = [3,5,7]
x = chinese_remainder_theorem(a, n)
print(f'Solution x = {x}')

When to Use Chinese Remainder Theorem

CRT helps in solving problems involving large numbers split into smaller modular computations, reducing complexity, and ensuring efficient algorithms in:

• Cryptography (RSA, secret sharing)
• Algorithm optimization for modular arithmetic
• Signal processing for reconstructing signals from samples
• Solving Diophantine equations in number theory

Limitations and Requirements

The key requirement for CRT applicability is pairwise coprime moduli. If moduli share factors, the direct application of CRT fails and alternative methods like the generalized CRT or system checks are needed.

Summary

The Chinese Remainder Theorem is an elegant and constructive theorem for solving modular systems by leveraging the coprimality of moduli. It guarantees unique solutions in a combined modulus space and enables practical applications where modular decomposition is beneficial. The stepwise approach and the Python example empower developers and students to implement and understand CRT effectively.