Chinese Remainder Theorem

Enter pairwise coprime moduli ni and residues ai. This page synthesizes the constructive CRT solution, explains why it works, and verifies the result with a built-in test harness.

Input

Format: x ≡ a (mod n), with n ≥ 2 and gcds(ni, nj) = 1.

Output

Answer
—
Modulus Π ni
—
Witness terms Σ aiMiyi
—

Reason Why

Let n1,…,nk be pairwise coprime and set N = ∏ ni.
For each i, define Mi = N / ni and choose yi with Mi·yi ≡ 1 (mod ni) (possible since gcd(Mi, ni) = 1).
Consider x = Σ aiMiyi (mod N).
For fixed i, we have Mj ≡ 0 (mod ni) when j ≠ i, hence x ≡ aiMiyi ≡ ai (mod ni).
Thus the system is satisfied.
If x and x′ both satisfy all congruences, then ni | (x − x′) for every i, so N | (x − x′).
Therefore the solution is unique modulo N.

Show constructive terms

Check (harness)

Preloaded Checks (harness)

Each block computes the constructive CRT solution, explains it, and verifies all congruences. We include a negative case to show failure on non‑coprime moduli.