CoreSource checked

Chinese Remainder Theorem Algorithm

Combines compatible congruences into one solution modulo the product of the moduli.

Explore relationships Open constellationBrowse atlas

Quick Facts

Compact metadata for implementation and discovery.

Category: Numerical Methods
Difficulty: Intermediate
Family: Number Theory
Tier: Core
Status: Verified
Review: Source Checked
Sources: 2
Formulas: 1
Relationships: 5
Code example: Ready
Visualization: Ready

Overview

The Chinese Remainder Theorem algorithm uses modular inverses to combine residues for pairwise coprime moduli into a single residue class.

Core Concepts

modular system solvingnumber theorymodular arithmeticnumerical methods

Quick facts

Complexity

Runtime and memory behavior at a glance.

Best

O(k)

Average

O(k^2)

Worst

O(k^3)

Space

O(k)

When to Use

Use it when moduli are pairwise coprime and residues must be combined.
Use it to reconstruct a value from modular residues.
Use extended Euclid to compute the required modular inverses.

When Not to Use

Avoid the simple form when moduli are not pairwise coprime.
Avoid it without checking residue compatibility for non-coprime variants.
Avoid unchecked multiplication when modulus products can overflow.

What It Does

Solves systems of congruences
Combines residues with modular inverses

Use Cases

Number-theory computations
Modular arithmetic reconstruction
Cryptographic arithmetic workflows

Inputs

Numbers, vectors, matrices, or functions
Tolerance or precision settings

Outputs

Computed numeric result
Residual, factorization, or approximation

Key Formulas (1)

CRT combination

x = ∑(a_i · M_i · inverse(M_i mod m_i)) mod M

x = sum(a_i * M_i * inverse(M_i mod m_i)) mod M

Combines residues into one solution modulo the product M.

Pseudocode

1.Validate input dimensions, conditioning, and numerical tolerance parameters for Chinese Remainder Theorem Algorithm.
2.Initialize the working buffers, basis vectors, or decomposition factors (modular system solving).
3.Execute the core numerical recurrence by Combines compatible congruences into one solution modulo the product of the moduli (x = sum(a_i * M_i * inverse(M_i mod m_i)) mod M).
4.Monitor residual error, stability bounds, or step convergence across iterations.
5.Return the computed number theory coefficients, factors, or transformed values.

Canonical Example

Input: x ≡ 2 mod 3, x ≡ 3 mod 5
Output: x ≡ 8 mod 15
Explanation: 8 has remainder 2 when divided by 3 and remainder 3 when divided by 5.

Implementation Notes

Compute the product of all moduli.
For each congruence, multiply its residue by the partial product and its modular inverse.
Normalize the final sum modulo the full product.

Common Pitfalls

Forgetting to verify pairwise coprime moduli.
Using a modular inverse when it does not exist.
Returning a negative representative without normalizing modulo the product.

Interactive Mechanism Walkthrough

Iterative Convergence & State Trajectory

Show combining congruences with modular inverses on a small modular system solving example.

Step 1 of 5: Validate input dimensions, conditioning, and numerical tolerance parameters for Chinese Remainder Theorem Algorithm.

numerical-methods-mechanism

Notes

Chinese Remainder Theorem Algorithm operates in O(k^2) time and O(k) space within the Number Theory family. Key governing relation: x = sum(a_i * M_i * inverse(M_i mod m_i)) mod M. Often compared with Extended Euclidean Algorithm and Binary GCD.

Sources (2)

What each reference supports for this entry.

Modern Computer Arithmetic

Book

Reference for Chinese Remainder Theorem Algorithm's arithmetic operations, modular arithmetic, multiplication, division, or number-theoretic implementation details.

Open source