Chinese Remainder Theorem

⚡ Key Takeaways

Chinese Remainder Theorem (CRT): A system of simultaneous congruences with pairwise coprime moduli has a unique solution modulo the product of those moduli. In words: if you know a number's remainders upon division by several coprime numbers, you can reconstruct the number uniquely (up to the product). It applies in number theory, abstract algebra, cryptography, and computer arithmetic. Known to the Chinese mathematician Sun Tzu (c. 3rd–5th century CE) and fully formalized by Gauss in 1801.

💡 The Core Insight

Coprime moduli carry independent information. Knowing $x \bmod n_1$ tells you nothing about $x \bmod n_2$ when $\gcd(n_1,n_2)=1$ , so the remainders can be chosen freely and combined uniquely. The "gluing" of these independent pieces into one number is exactly a ring isomorphism, and it works precisely because coprimality lets you build "indicator" elements that are $1$ in one component and $0$ in the others.

DefinitionSystem of Congruences

Let $n_1, n_2, \dots, n_k$ be positive integers and $a_1, a_2, \dots, a_k$ be integers. A system of simultaneous congruences is

1

\quad x \equiv a_1 \pmod{n_1}, \quad x \equiv a_2 \pmod{n_2}, \quad \dots, \quad x \equiv a_k \pmod{n_k}.

Derivation hint: This is simply a list of independent divisibility constraints $n_i \mid (x - a_i)$ . Here $x$ is the unknown integer, each $a_i$ is the required residue modulo $n_i$ , and the moduli $n_i$ are said to be pairwise coprime if $\gcd(n_i, n_j) = 1$ for all $i \neq j$ .

TheoremChinese Remainder Theorem — Classical Form

If the moduli $n_1, \dots, n_k$ are pairwise coprime and $N = \prod_{i=1}^{k} n_i$ , then the system [1] has a solution $x$ , and this solution is unique modulo $N$ . That is, there is exactly one residue class $x \bmod N$ satisfying all $k$ congruences. An explicit solution is given by

2

\quad x \equiv \sum_{i=1}^{k} a_i\, N_i\, M_i \pmod{N}, \qquad N_i = \frac{N}{n_i}, \qquad M_i \equiv N_i^{-1} \pmod{n_i}.

Derivation hint: $N_i$ is divisible by every $n_j$ with $j\neq i$ , so the $i$ -th term acts as a "selector" that is $a_i$ mod $n_i$ and $0$ mod the others.

TheoremChinese Remainder Theorem — Ring-Theoretic Form

If $n_1, \dots, n_k$ are pairwise coprime with product $N$ , the natural reduction map is a ring isomorphism:

3

\quad \mathbb{Z}/N\mathbb{Z} \;\cong\; \mathbb{Z}/n_1\mathbb{Z} \times \mathbb{Z}/n_2\mathbb{Z} \times \cdots \times \mathbb{Z}/n_k\mathbb{Z}, \qquad x \bmod N \longmapsto (x \bmod n_1, \dots, x \bmod n_k).

Derivation hint: The map is well-defined and injective because pairwise coprimality forces $N \mid (x-y)$ from $n_i \mid (x-y)$ for all $i$ ; surjectivity follows by counting, since both sides have $N$ elements. Restricting to units gives the multiplicative version, useful for Euler's Totient Function:

4

\quad (\mathbb{Z}/N\mathbb{Z})^\times \;\cong\; (\mathbb{Z}/n_1\mathbb{Z})^\times \times \cdots \times (\mathbb{Z}/n_k\mathbb{Z})^\times, \qquad \varphi(N) = \prod_{i=1}^k \varphi(n_i).

Derivation hint: An element is a unit iff it is a unit in each component; multiplicativity of $\varphi$ then follows from the cardinality of the right-hand product.

ProofExistence and Uniqueness (Classical)

Step 1 — Build the selectors. For each $i$ , set $N_i = N/n_i = \prod_{j \neq i} n_j$ . Since the $n_j$ are pairwise coprime, $N_i$ is coprime to $n_i$ (no $n_j$ with $j \neq i$ shares a factor with $n_i$ ). Therefore $N_i$ is invertible modulo $n_i$ , and there exists $M_i$ with

5

\quad N_i M_i \equiv 1 \pmod{n_i}.

Derivation hint: $\gcd(N_i, n_i)=1$ guarantees an inverse by <a class="wiki-link" href="/wiki/math-numthy-bezout-identity">Bézout's Identity</a>; compute $M_i$ via the <span class="wiki-link-missing">Extended Euclidean Algorithm</span>.

Step 2 — Verify the candidate. Define $x = \sum_{i=1}^k a_i N_i M_i$ . Fix an index $r$ . For $i \neq r$ , the term $a_i N_i M_i$ contains the factor $n_r$ (since $n_r \mid N_i$ ), so it vanishes mod $n_r$ . For $i = r$ ,

6

\quad a_r N_r M_r \equiv a_r \cdot 1 = a_r \pmod{n_r}.

Derivation hint: Use [5] with $i=r$ to replace $N_r M_r$ by $1$ modulo $n_r$ . Hence $x \equiv a_r \pmod{n_r}$ for every $r$ , so $x$ solves the system.

Step 3 — Uniqueness. Suppose $x$ and $y$ both solve [1]. Then $n_i \mid (x - y)$ for all $i$ . Because the $n_i$ are pairwise coprime, their product divides the difference:

7

\quad n_i \mid (x-y)\ \forall i \;\Longrightarrow\; N = \operatorname{lcm}(n_1,\dots,n_k) \mid (x-y).

Derivation hint: For pairwise coprime moduli, $\operatorname{lcm} = \prod n_i = N$ ; a number divisible by each coprime factor is divisible by their product. Thus $x \equiv y \pmod{N}$ , proving uniqueness modulo $N$ . $\blacksquare$

∎

⚠️ Pairwise vs. Mutually Coprime

Step 3 requires pairwise coprimality, not merely that $\gcd(n_1,\dots,n_k)=1$ collectively. The moduli $6, 10, 15$ satisfy $\gcd(6,10,15)=1$ but are not pairwise coprime, and CRT in its clean form fails for them.

mathematician · Carl Friedrich Gauss | 1777–1855

While the problem dates to ancient China, it was Gauss who gave the theorem its rigorous modern treatment in his 1801 masterwork Disquisitiones Arithmeticae. Gauss introduced the congruence notation $\equiv$ still used today and systematically developed the theory of residues, placing the Chinese Remainder Theorem within a coherent algebraic framework. His viewpoint anticipated the ring-isomorphism formulation that abstract algebra would later make precise, and his constructive method for combining congruences is essentially the selector argument given above.

🧠 Intuition

Think of an odometer with several independent dials, each cycling at a different coprime period — one resets every $3$ clicks, one every $5$ , one every $7$ . Because the periods share no common factor, the dials only realign after $3 \times 5 \times 7 = 105$ clicks. During those $105$ steps, every combination of dial positions occurs exactly once. So specifying where each dial points pins down the click count uniquely within one full cycle. The CRT says reading the dials (the remainders) and reading the odometer (the number mod $105$ ) are two equivalent languages for the same information — and pairwise coprimality is precisely what makes the dials independent.

Figure

CRT as independent cycling clocks: residues mod 3 and mod 5 align uniquely every 15 steps

```svg

```

ExampleSun Tzu's Classic Problem

Given: Find the smallest positive $x$ with

x \equiv 2 \pmod 3, \quad x \equiv 3 \pmod 5, \quad x \equiv 2 \pmod 7.

Step 1 — Product and selectors. $N = 3\cdot 5\cdot 7 = 105$ . $N_1 = 105/3 = 35$ , $N_2 = 105/5 = 21$ , $N_3 = 105/7 = 15$ .

Step 2 — Inverses (the $M_i$ ). $35 \equiv 2 \pmod 3$ , need $2 M_1 \equiv 1 \pmod 3 \Rightarrow M_1 = 2$ . $21 \equiv 1 \pmod 5 \Rightarrow M_2 = 1$ . $15 \equiv 1 \pmod 7 \Rightarrow M_3 = 1$ .

Step 3 — Combine via [2].

x \equiv 2\cdot 35\cdot 2 + 3\cdot 21\cdot 1 + 2\cdot 15\cdot 1 = 140 + 63 + 30 = 233 \pmod{105}.

Step 4 — Reduce. $233 - 2\cdot 105 = 23$ .

Answer: $\boxed{x \equiv 23 \pmod{105}}$ (check: $23 = 7\cdot3+2$ , $23=4\cdot5+3$ , $23=3\cdot7+2$ ✓).

ExampleTwo-Congruence Sequential Substitution

Given: Solve $x \equiv 4 \pmod 9$ and $x \equiv 7 \pmod{11}$ .

Step 1 — Parametrize the first. $x = 4 + 9t$ for integer $t$ .

Step 2 — Substitute into the second. $4 + 9t \equiv 7 \pmod{11} \Rightarrow 9t \equiv 3 \pmod{11}.$

Step 3 — Invert $9$ mod $11$ . Since $9 \cdot 5 = 45 \equiv 1 \pmod{11}$ , multiply: $t \equiv 5\cdot 3 = 15 \equiv 4 \pmod{11}$ .

Step 4 — Back-substitute. $t = 4 + 11s$ , so $x = 4 + 9(4 + 11s) = 40 + 99s$ .

Answer: $\boxed{x \equiv 40 \pmod{99}}$ (check: $40 = 4\cdot9+4$ , $40=3\cdot11+7$ ✓). Note $N = 9\cdot 11 = 99$ .

⚠️ CRT Does Not Require Prime Moduli

A frequent error is to assume the moduli must be primes. They need only be pairwise coprime. For instance $8, 9, 25$ are pairwise coprime (and composite), and CRT applies perfectly with $N = 1800$ . Conversely, primality alone is not the issue — repeated primes like $4, 8$ break coprimality.

CounterexampleNon-Coprime Moduli Can Have No Solution

Consider

x \equiv 1 \pmod 4, \qquad x \equiv 2 \pmod 6.

Here $\gcd(4,6) = 2 \neq 1$ . The first congruence forces $x$ odd; the second forces $x$ even (since $x \equiv 2 \pmod 6$ means $x$ is even). These contradict, so no solution exists. A solution exists for non-coprime moduli only if the congruences agree on common factors: $a_i \equiv a_j \pmod{\gcd(n_i,n_j)}$ . When they do agree, the solution is unique modulo $\operatorname{lcm}(n_1,\dots,n_k)$ , not the product.

connection

CRT sits at a crossroads of algebra and number theory. Its unit-group form [4] gives the multiplicativity of <a class="wiki-link" href="/wiki/eulers-totient-function">Euler's Totient Function</a>, $\varphi(mn)=\varphi(m)\varphi(n)$ for coprime $m,n$ . The constructive solution leans on the Extended Euclidean Algorithm and Bézout's Identity to compute inverses. The ring isomorphism [3] is the prototype of decomposing a Quotient Ring into a product, and it generalizes to comaximal ideals in any commutative ring — the same statement holds for $R/(I_1 \cap \cdots \cap I_k)$ when the ideals are pairwise comaximal. In the structure theory of finite abelian groups, CRT is what lets $\mathbb{Z}/N\mathbb{Z}$ split into its primary components $\mathbb{Z}/p^e\mathbb{Z}$ . It also underlies Fermat's Little Theorem applications when assembling results across prime factors.

🔬 Where this appears

⏳ History

- c. 3rd–5th century CE: The Chinese mathematician Sun Tzu poses the "counting in threes, fives, sevens" problem in Sunzi Suanjing, the earliest known statement.

- c. 7th century: Indian mathematician Brahmagupta develops the kuttaka method for linear indeterminate equations, closely related to CRT computations.

- 1247: Qin Jiushao publishes the Mathematical Treatise in Nine Sections, giving the first complete general algorithm (Dayan method) for the case of non-coprime moduli.

- 1500s–1600s: European mathematicians, including Fibonacci earlier and later commentators, treat scattered instances of remainder problems.

- 1734: Leonhard Euler works on systems of congruences in the context of number theory.

- 1801: Carl Friedrich Gauss formalizes the theorem in Disquisitiones Arithmeticae, introducing congruence notation and the modern proof.

- late 1800s: Richard Dedekind and the rise of ideal theory recast CRT abstractly, anticipating the ring-isomorphism form.

- 20th century: Emmy Noether and others generalize CRT to commutative rings with comaximal ideals, making [3] a standard structural theorem.

- 1970s–present: CRT becomes computationally central in cryptography (RSA, 1977) and computer algebra.

open-problem

While the CRT itself is fully proved, its applications touch open and hard questions. Reconstructing an integer from residues is trivial, but the inverse problem with errors — recovering a number from noisy or partially corrupted residues — leads to the CRT decoding problem, whose hardness underpins certain lattice-based and number-theoretic cryptosystems. In computational number theory, the efficiency of CRT-based algorithms depends on factoring or on knowing the moduli, and questions about the distribution of residues (e.g., how "random" CRT-reconstructed values behave) connect to deep conjectures in analytic number theory. Generalizing CRT to non-commutative rings and to module-theoretic settings is well understood, but the interplay between CRT and the difficulty of integer factorization keeps it at the heart of computational complexity questions.

Formal Statement

Why It Holds / Derivation

Building Intuition

Worked Examples

Common Misconceptions

Connections

Real-World Applications

Historical Development

Subtleties & Limits

See Also