Chinese Remainder Theorem

ℤ/mn ℤ/m × ℤ/n for coprime m, n.

The idea

Theorem (Chinese Remainder Theorem).

Let $m$ and $n$ be coprime integers, meaning $\gcd(m, n) = 1$. Then for any residues $a$ and $b$ there is exactly one $x$ modulo $mn$ with $x \equiv a \pmod{m} \quad\text{and}\quad x \equiv b \pmod{n}.$ Equivalently, the reduction map $\mathbb{Z}/mn\mathbb{Z} \to \mathbb{Z}/m\mathbb{Z} \times \mathbb{Z}/n\mathbb{Z}$ sending $x$ to the pair $(x \bmod m,\, x \bmod n)$ is an isomorphism of rings.

The first statement says that two congruence conditions with coprime moduli never conflict and never leave the solution undetermined: a common solution exists, and it is unique modulo the product. The second says that knowing a number modulo $m$ and modulo $n$ amounts to knowing it modulo $mn$, so we can carry out arithmetic modulo $mn$ in the two smaller rings independently and reassemble the results.

The hypothesis is essential: when $m$ and $n$ share a factor, the two conditions can contradict each other, and even when they do not, they determine $x$ only modulo a number smaller than $mn$.

Algorithm.

Algorithm: Solving the System Input: coprime moduli m and n, residues a and b Output: the unique solution x modulo mn 1. find integers u and v with mu + nv = 1 // by the extended Euclidean algorithm; gcd(m, n) = 1 guarantees they exist 2. x = a·(nv) + b·(mu) // mod m: nv ≡ 1 and mu ≡ 0, so x ≡ a; mod n the roles swap 3. reduce x modulo mn, return the result // the one solution in {0, 1, ..., mn − 1}

Ways to work on it

• Walkthrough. Solve coprime congruences and the ring isomorphism.
• Proof. See why — is an injection between equal-size sets, hence a bijection, with the Bezout formula for the inverse.
• Practice. Solve a pair of coprime congruences.
• Hardest. A three-modulus system.

Not sure where to start? Take the ten-question placement test.