Chinese remainder theorem ($\mathbb{Z}/M\mathbb{Z}\cong {\prod }_j\mathbb{Z}/m_j\mathbb{Z}$)

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.

Choose a primitive root $g$ modulo $p$ and write the nonzero coefficients $3,5,7$ as $g^a,g^b,g^c$. The Chinese remainder theorem gives an exponent $r$ congruent to $a,b,c$ modulo $3,5,7$, respectively. Then $n=g^r$ and the three roots $g^{(r-a)/3}$, $g^{(r-b)/5}$, $g^{(r-c)/7}$ give the displayed common nonzero residue. This technique converts multiplicative power constraints into simultaneous additive modular congruences for exponents.

Let $q_1,\dots ,q_r$ be distinct prime numbers and $a_1,\dots ,a_r$ positive integers. There are infinitely many positive integers $n$ with $q_i^{a_i}\mid n+i$ for every $i$. Indeed the moduli $q_i^{a_i}$ are pairwise coprime, so the Chinese remainder theorem solves $n\equiv -i(\mathrm{mod}{q}_i^{a_i})$ simultaneously. Adding multiples of their product gives arbitrarily large positive solutions. This allows long runs in which every integer has a large prescribed prime power divisor, even though neighboring integers are coprime.

For positive integer moduli $m,n$, the simultaneous integer congruences $x\equiv a(\mathrm{mod}m)$ and $x\equiv b(\mathrm{mod}n)$ are solvable exactly when $a\equiv b(\mathrm{mod}\gcd (m,n))$. When solvable, they determine a unique congruence class modulo $\mathrm{lcm}(m,n)$. To see the condition, put $x=a+mk$: the remaining equation is the linear congruence $mk\equiv b-a(\mathrm{mod}n)$, which is solvable exactly when the greatest common divisor divides $b-a$.

For example, $x\equiv 1(\mathrm{mod}6)$ and $x\equiv 3(\mathrm{mod}8)$ give $6k\equiv 2(\mathrm{mod}8)$, hence $3k\equiv 1(\mathrm{mod}4)$ and $k\equiv 3(\mathrm{mod}4)$. Thus $x\equiv 19(\mathrm{mod}24)$. Changing the second remainder to two makes the conditions incompatible: the first requires an odd integer, while the second requires an even integer. Article 32 of Carl Friedrich Gauss's Disquisitiones arithmeticae gives a successive construction for simultaneous remainders, including the greatest common divisor and least common multiple that enter this general case. ^[ref]

For pairwise comaximal ideals in a commutative ring, reduction has the displayed ring isomorphism. The kernel is their intersection, equal to their product. Choose $e_i\in {\prod }_{j\ne i}{I}_j$ with $e_i\equiv 1(\mathrm{mod}{I}_i)$; then ${\sum }_i{a}_i{e}_i$ lifts any prescribed residue tuple. The equality between intersection and product follows from $1=u+v$, $u\in I$, $v\in J$, which writes each $x\in I\cap J$ as $xu+xv\in IJ$.

For a positive integer $b={\prod }_i{p}_i^{n_i}$, every rational number $a/b$ has a unique representation $a/b=n+{\sum }_i{q}_i/p_i^{n_i}$ with $n\in \mathbb{Z}$ and $0\le q_i<p_i^{n_i}$. With $B_i=b/p_i^{n_i}$, the coefficients satisfy $q_i\equiv a{B}_i^{-1}(\mathrm{mod}{p}_i^{n_i})$. Their existence and uniqueness use modular multiplicative inverses and the Chinese remainder theorem.

A nonzero polynomial of degree $d$ over a field has at most $d$ roots. In particular, if a polynomial congruence $f(x)\equiv 0(\mathrm{mod}p)$ has degree $d$ and not all coefficients are divisible by the prime $p$, it has at most $d$ incongruent solutions modulo $p$.

For coprime $m,n$, reduction gives $(\mathbb{Z}/mn\mathbb{Z}{)}^{\times }\cong (\mathbb{Z}/m\mathbb{Z}{)}^{\times }\times (\mathbb{Z}/n\mathbb{Z}{)}^{\times }$.

The order of a unit modulo a product of coprime moduli is the least common multiple of the orders of its components.