Chinese remainder theorem

The Chinese remainder theorem says that remainders modulo pairwise coprime positive integers can be specified independently. For $m_1,\dots ,m_r$ pairwise coprime and $M=m_1\cdots m_r$, every prescribed list $a_1,\dots ,a_r$ determines one congruence class modulo $M$ satisfying $x\equiv a_j(\mathrm{mod}{m}_j)$ for all $j$. It determines a class, rather than one unrestricted integer: adding a multiple of $M$ preserves every remainder.

For example, combine $x\equiv 2(\mathrm{mod}3)$ and $x\equiv 3(\mathrm{mod}5)$. Write $x=2+3k$ from the first condition. The second becomes $3k\equiv 1(\mathrm{mod}5)$. Since three has modular inverse two modulo five, $k\equiv 2(\mathrm{mod}5)$, giving $x\equiv 8(\mathrm{mod}15)$. The integers $8$, $23$ and $-7$ all work. The fifteen possibilities modulo fifteen correspond to the fifteen pairs in a three-by-five grid.

The theorem also preserves arithmetic: reducing an addition or a multiplication modulo each $m_j$ gives the same tuple as performing that operation on the corresponding congruence classes. In the language of quotient rings, reduction is a ring isomorphismOne large residue is thus an exact encoding of several smaller residues. This is useful for splitting arithmetic into smaller calculations and then reconstructing the result; MIT's modular arithmetic notes develop both the reconstruction and the product representation. ^[ref] For a concrete multiplication, $7$ corresponds to $(1,2)$ and $8$ to $(2,3)$ modulo $(3,5)$. Their componentwise product is $(2,1)$, which reconstructs to $11(\mathrm{mod}15)$, agreeing with $56\equiv 11(\mathrm{mod}15)$.

A constructive formula explains the independence. For $m_j>1$, put $M_j=M/m_j$ and choose $u_j$ with $M_j{u}_j\equiv 1(\mathrm{mod}{m}_j)$, using a modular multiplicative inverse. Then $e_j=M_j{u}_j$ is one modulo $m_j$ and zero modulo every other $m_i$. Thereforehas the desired remainders. A modulus equal to one imposes no restriction and can be omitted. Uniqueness follows because a difference divisible by every $m_j$ is divisible by their product when they are pairwise coprime. This short construction gives a reusable algorithm as well as an existence statement.

The coprime hypothesis explains why every cell in the left grid is attainable. With integer moduli six and eight, a pair must agree modulo their greatest common divisor, two. There are twenty-four compatible pairs, rather than forty-eight arbitrary pairs; each corresponds to a class modulo the least common multiple, twenty-four. The Chinese remainder theorem for noncoprime moduli states the resulting compatibility rule.