ℕ

Chinese Remainder Theorem

Undergraduate

Definition

A system of congruences with pairwise coprime moduli has a unique solution. It allows decomposing large computations into smaller ones.

x ≡ a₁ ±odn₁, …, x ≡ aₖ ±odnₖ

System of congruences

x ≡ ∑ᵢ aᵢ Nᵢ Mᵢ ±odN

Solution formula (N = n₁...nₖ, Nᵢ = N/nᵢ, MᵢNᵢ ≡ 1 mod nᵢ)

Example 1

Find x where x ≡ 2 (mod 3), x ≡ 3 (mod 5).

Discovered by: Sunzi (Chinese mathematician) (c. 3rd century)

First appeared in Sunzi Suanjing, famous for counting soldiers problem.

RSA decryption speedup

Large number decomposition

Periodic event calculation