Chinese Remainder Theorem

Merge modular congruences with inverses to reconstruct the unique solution modulo the product.

Core idea

For pairwise coprime moduli, construct one basis term per congruence. That term is one under its own modulus and zero under all others, so weighted terms combine independently.

Read the visualization

Each table row builds its partial product, modular inverse, and residue term. The final row adds them and reduces the sum by the full modulus product.

	r	m
congruence ①	2	3
congruence ②	3	5
congruence ③	2	7
total

Multiply the pairwise coprime moduli to obtain the combined period M.

1function crt(rs: number[], ms: number[]): number {
const M = ms.reduce((p, m) => p * m, 1); // init prime 
let x = 0;
for (let i = 0; i < ms.length; i++) {
  const Mi = M / ms[i];             // mi: mi down  ≡ 0
  const ti = modInverse(Mi, ms[i]); //  expand inv compute inv:  current inv down inv 1
  x += rs[i] * Mi * ti;             // term congruence term term 
}
return x % M;                       //  merge, mod M sum one 
10}

congruence systemx≡2 (mod 3), x≡3 (mod 5), x≡2 (mod 7)

M3·5·7 = 105

1 / 12

Complexity and tradeoffs

Time: O(k log M). Space: O(k). The direct form assumes pairwise coprime moduli; generalized merging checks gcd compatibility.

Invariant: After a basis term is built, it contributes its requested residue to exactly one congruence and contributes zero to every other congruence.

Where it fits

CRT reconstructs values from modular channels, accelerates large-integer arithmetic, and schedules repeating cycles. Non-coprime moduli require compatibility checks and generalized merging.

Algorithm Visualizer

Chinese Remainder Theorem

Core idea

Read the visualization

Complexity and tradeoffs

Where it fits