Chinese Remainder Theorem

Statement

If m₁,…,mₖ are pairwise coprime, the system x≡aᵢ (mod mᵢ) has a unique solution mod M=m₁⋯mₖ.

Examples

In Depth

The Chinese Remainder Theorem (CRT) has been known in China since the 3rd century CE (Sun Tzu's Mathematical Classic). It states that a system of simultaneous congruences with pairwise coprime moduli has a unique solution modulo the product of the moduli.

The CRT has a constructive proof: the solution is \(x=\sum_i a_i M_i y_i\pmod{M}\) where \(M=\prod m_i\), \(M_i=M/m_i\), and \(y_i=M_i^{-1}\pmod{m_i}\). This construction is used in fast multi-precision arithmetic and in the RSA algorithm (CRT form of RSA is about 4× faster).

In abstract algebra, CRT is the statement \(\mathbb{Z}/M\mathbb{Z}\cong\prod_i\mathbb{Z}/m_i\mathbb{Z}\) as rings. This ring isomorphism generalizes to any principal ideal domain and is a special case of the structure theorem for modules over PIDs.

Further Reading & Context

The Chinese Remainder Theorem (CRT): if \(n_1,\ldots,n_k\) are pairwise coprime, then the system \(x\equiv a_i\pmod{n_i}\) has a unique solution modulo \(N=n_1\cdots n_k\). The solution is \(x=\sum a_i M_i y_i\bmod N\) where \(M_i=N/n_i\) and \(y_i=M_i^{-1}\bmod n_i\).

The CRT gives an isomorphism \(\mathbb{Z}/N\mathbb{Z}\cong\mathbb{Z}/n_1\mathbb{Z}\times\cdots\times\mathbb{Z}/n_k\mathbb{Z}\). This means arithmetic modulo \(N\) can be done component-wise modulo each \(n_i\), then reconstructed. This is used in fast arithmetic and in multi-precision computation.

CRT in cryptography: RSA decryption is faster using CRT. Instead of computing \(c^d\bmod n\) directly, compute \(c^{d_p}\bmod p\) and \(c^{d_q}\bmod q\) (where \(d_p=d\bmod(p-1)\), \(d_q=d\bmod(q-1)\)), then combine with CRT. This gives a 4× speedup.

Garner's algorithm reconstructs an integer from its residues using a mixed-radix representation, avoiding large intermediate values. It is used in computer algebra systems for modular arithmetic with multiple moduli.

The CRT generalizes to rings: if \(I_1,\ldots,I_k\) are pairwise coprime ideals in a ring \(R\), then \(R/(I_1\cap\cdots\cap I_k)\cong R/I_1\times\cdots\times R/I_k\). This is used in algebraic number theory and commutative algebra.

Deep Dive: Chinese Remainder Theorem

This lesson extends core ideas for chinese remainder theorem with rigorous reasoning, edge-case checks, and application framing in number theory.

Practice Set

References & Editorial Notes

• Stewart, Calculus.
• Strang, Introduction to Linear Algebra.
• Apostol, Mathematical Analysis.

Last editorial review: 2026-04-14.