Chinese Remainder Theorem

Chinese Remainder Theorem

The Chinese Remainder Theorem (CRT) is a fundamental result in number theory that describes when and how a system of congruences can be solved simultaneously. It has applications in cryptography, computer science, and abstract algebra.

Statement

Let (n_1),(n_2),…,(n_k) be pairwise coprime positive integers (gcd((n_i),(n_j))=1 for i≠j). Then the system of congruences:

x≡(a_1)*(mod((n_1))),x≡(a_2)*(mod((n_2))),…,x≡(a_k)*(mod((n_k)))

has a unique solution modulo N=(n_1)*(n_2)⋯(n_k).

Constructive Proof

Let (N_i)=N/(n_i) for each i. Since gcd((N_i),(n_i))=1, there exists (M_i) such that (N_i)*(M_i)≡1*(mod((n_i))).

The solution is:

x=(∑_i=1^k)((a_i))*(N_i)*(M_i)*(mod(N))

Ring-Theoretic Formulation

CRT states there is a ring isomorphism:

ℤ/N*ℤ≅ℤ/(n_1)*ℤ×ℤ/(n_2)*ℤ×⋯×ℤ/(n_k)*ℤ

This generalizes to ideals in any ring: if I and J are coprime ideals, then R/(I∩J) is isomorphic to R/I×R/J.

Applications

RSA Decryption

CRT speeds up RSA decryption by computing md*mod(p) and md*mod(q) separately, then combining using CRT. This is about 4 times faster than direct computation.

Secret Sharing

Shamirs secret sharing uses CRT ideas: a secret is split into shares that can be recombined when enough shares are present.

Computer Arithmetic

Residue number systems use CRT for parallel computation. Operations mod different primes can proceed independently and be combined at the end.

Calendar Calculations

Computing Easter dates and finding when calendar cycles repeat uses systems of congruences solved by CRT.

Generalization to Polynomials

CRT applies to polynomials: given coprime polynomials (ƒ_1),…,(ƒ_k), a polynomial can be uniquely determined mod (ƒ_1)⋯(ƒ_k) from its remainders mod each (ƒ_i).

This is the basis for Lagrange interpolation and fast polynomial multiplication.

Algorithm Complexity

Finding the solution requires computing modular inverses (via extended Euclidean algorithm) and combining terms. Total complexity is O*(k*(log_)2(N)) using fast algorithms.

When Moduli Are Not Coprime

If gcd((n_1),(n_2))=d>1, the system x≡(a_1)*(mod((n_1))),x≡(a_2)*(mod((n_2))) has a solution iff (a_1)≡(a_2)*(mod(d)).

Historical Origin

The theorem appears in the 3rd-century Chinese text Sunzi Suanjing. The problem asks: find a number that leaves remainder 2 when divided by 3, remainder 3 when divided by 5, and remainder 2 when divided by 7.

Garners Algorithm

An efficient algorithm for CRT that avoids large intermediate values by computing the solution incrementally.

CRT and Eulers Totient

CRT implies φ*((n_1)*(n_2))=φ((n_1))*φ((n_2)) when gcd((n_1),(n_2))=1, since the units mod (n_1)*(n_2) decompose as products.

Explicit Formula

For two moduli (n_1) and (n_2) with gcd((n_1),(n_2))=1:

x=(a_1)*(n_2)*((n_2)(−1)*mod((n_1)))+(a_2)*(n_1)*((n_1)(−1)*mod((n_2)))*(mod((n_1)*(n_2)))

Simultaneous Congruences

CRT allows solving systems like x≡1*(mod(2)),2*(mod(3)),3*(mod(5)),4*(mod(7)) by working with each congruence independently.

Idempotents

The isomorphism in CRT is given by idempotent elements. If (e_i) is 1*(mod((n_i))) and 0*(mod((n_j))) for j≠i, then x=(∑_^)((a_i))*(e_i).

CRT for Groups

For abelian groups: if G has order n=(n_1)*(n_2) with gcd((n_1),(n_2))=1, then G is isomorphic to (G_1)×(G_2) where |(G_1)|=(n_1) and |(G_2)|=(n_2).

Iterative Solution

For many congruences, solve two at a time. Combine x≡a*(mod(m)) and x≡b*(mod(n)) into x≡c*(mod(m*n)), then continue with remaining congruences.

Error Detection

CRT enables redundant computation for error detection: compute a result mod several primes and check consistency.

Uniqueness

The solution is unique modulo N, the product of all moduli. Different representatives of the same residue class are congruent mod N.

Summary

CRT states: working mod (n_1)*(n_2)⋯(n_k) (coprime factors) is equivalent to working mod each (n_i) separately. This decomposition is fundamental in number theory, algebra, and computer science.

The theorem transforms hard problems mod large N into easier problems mod smaller factors.