Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

For questions related to the Chinese Remainder Theorem and its applications.

In number theory and algebra, the Chinese Remainder Theorem states that if $n_1, ..., n_k$ are positive, pairwise relatively prime integers, and $a_1, ..., a_k$ is any collection of integers, there is a unique solution to the system of congruences

$$x \equiv a_1 \pmod{n_1}$$ $$x \equiv a_2 \pmod{n_2}$$ $$\vdots$$ $$x \equiv a_k \pmod{n_k}$$

modulo the product $n_1 n_2 \cdots n_k$.

More generally, consider a principal ideal domain $R$. If $u_1, ..., u_k$ are pairwise relatively prime elements of $R$ and $u = u_1 \cdots u_k$, then there is an isomorphism

$$R/uR \cong R/u_1 R \times \cdots \times R/u_k R$$

by the map

$$x + uR \mapsto (x + u_1 R, ..., x + u_k R)$$

Reference: Chinese remainder theorem.

history | excerpt history