Namespaces
Variants
Actions

Chinese remainder theorem

From Encyclopedia of Mathematics
Jump to: navigation, search


Let $A$ be a commutative ring with identity and let $\mathfrak a_1,\dots,\mathfrak a_n$ be a collection of ideals in $A$ such that $\mathfrak a_i+\mathfrak a_j=A$ for any $i\neq j$. Then, given any set of elements $x_1,\dots,x_n\in A$, there exists an $x\in A$ such that $x\equiv x_i\pmod{\mathfrak a_i}$, $i=1,\dots,n$. In the particular case when $A$ is the ring of integers $\mathbf Z$, the Chinese remainder theorem states that for any set of pairwise coprime numbers $a_1,\dots,a_n$ there is an integer $x$ giving pre-assigned remainders on division by $a_1,\dots,a_n$. In this form the Chinese remainder theorem was known in ancient China; whence the name of the theorem.

The most frequent application of the Chinese remainder theorem is in the case when $A$ is a Dedekind ring and $\mathfrak a_1=\mathfrak p_1^{s_1},\dots,\mathfrak a_n=\mathfrak p_n^{s_n}$, where the $\mathfrak p_1,\dots,\mathfrak p_n$ are distinct prime ideals in $A$. (If $\mathfrak a_1,\dots,\mathfrak a_n$ satisfy the condition of the theorem, then so do $\mathfrak a_1^{s_1},\dots,\mathfrak a_n^{s_n}$ for any natural numbers $s_1,\dots,s_n$.) In this case, the Chinese remainder theorem implies that for any set $s_1,\dots,s_n$ there exists an $x\in A$ such that the decomposition of the principal ideal $(x)$ into a product of prime ideals has the form

$$(x)=\mathfrak p_1^{s_1}\dots\mathfrak p_n^{s_n}\mathfrak q_1^{t_1}\dots\mathfrak q_m^{t_m}\quad(m\geq0),$$

where the ideals $\mathfrak p_1,\dots,\mathfrak p_n,\mathfrak q_1,\dots,\mathfrak q_m$ are pairwise distinct (the theorem on the independence of exponents).

References

[1] A.I. Kostrikin, "Introduction to algebra" , Springer (1982) (Translated from Russian)
[2] S. Lang, "Algebra" , Addison-Wesley (1974)
[3] S. Lang, "Algebraic numbers" , Addison-Wesley (1964)
How to Cite This Entry:
Chinese remainder theorem. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Chinese_remainder_theorem&oldid=43250
This article was adapted from an original article by L.V. Kuz'min (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article