Namespaces
Variants
Actions

Difference between revisions of "Chinese remainder theorem"

From Encyclopedia of Mathematics
Jump to: navigation, search
m (link)
(TeX)
 
Line 1: Line 1:
Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c022/c022120/c0221201.png" /> be a commutative [[ring with identity]] and let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c022/c022120/c0221202.png" /> be a collection of ideals in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c022/c022120/c0221203.png" /> such that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c022/c022120/c0221204.png" /> for any <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c022/c022120/c0221205.png" />. Then, given any set of elements <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c022/c022120/c0221206.png" />, there exists an <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c022/c022120/c0221207.png" /> such that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c022/c022120/c0221208.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c022/c022120/c0221209.png" />. In the particular case when <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c022/c022120/c02212010.png" /> is the ring of integers <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c022/c022120/c02212011.png" />, the Chinese remainder theorem states that for any set of pairwise coprime numbers <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c022/c022120/c02212012.png" /> there is an integer <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c022/c022120/c02212013.png" /> giving pre-assigned remainders on division by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c022/c022120/c02212014.png" />. In this form the Chinese remainder theorem was known in ancient China; whence the name of the theorem.
+
{{TEX|done}}
  
The most frequent application of the Chinese remainder theorem is in the case when <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c022/c022120/c02212015.png" /> is a [[Dedekind ring|Dedekind ring]] and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c022/c022120/c02212016.png" />, where the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c022/c022120/c02212017.png" /> are distinct prime ideals in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c022/c022120/c02212018.png" />. (If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c022/c022120/c02212019.png" /> satisfy the condition of the theorem, then so do <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c022/c022120/c02212020.png" /> for any natural numbers <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c022/c022120/c02212021.png" />.) In this case, the Chinese remainder theorem implies that for any set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c022/c022120/c02212022.png" /> there exists an <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c022/c022120/c02212023.png" /> such that the decomposition of the principal ideal <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c022/c022120/c02212024.png" /> into a product of prime ideals has the form
+
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.
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c022/c022120/c02212025.png" /></td> </tr></table>
+
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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c022/c022120/c02212026.png" /> are pairwise distinct (the theorem on the independence of exponents).
+
$$(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)
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