Difference between revisions of "Chinese remainder theorem"
(Importing text file) |
(TeX) |
||
(One intermediate revision by one other user not shown) | |||
Line 1: | Line 1: | ||
− | + | {{TEX|done}} | |
− | + | 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|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 | |
− | where the ideals | + | $$(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==== | ====References==== | ||
<table><TR><TD valign="top">[1]</TD> <TD valign="top"> A.I. Kostrikin, "Introduction to algebra" , Springer (1982) (Translated from Russian)</TD></TR><TR><TD valign="top">[2]</TD> <TD valign="top"> S. Lang, "Algebra" , Addison-Wesley (1974)</TD></TR><TR><TD valign="top">[3]</TD> <TD valign="top"> S. Lang, "Algebraic numbers" , Addison-Wesley (1964)</TD></TR></table> | <table><TR><TD valign="top">[1]</TD> <TD valign="top"> A.I. Kostrikin, "Introduction to algebra" , Springer (1982) (Translated from Russian)</TD></TR><TR><TD valign="top">[2]</TD> <TD valign="top"> S. Lang, "Algebra" , Addison-Wesley (1974)</TD></TR><TR><TD valign="top">[3]</TD> <TD valign="top"> S. Lang, "Algebraic numbers" , Addison-Wesley (1964)</TD></TR></table> |
Latest revision as of 13:31, 11 July 2018
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) |
Chinese remainder theorem. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Chinese_remainder_theorem&oldid=11578