View Shopping Cart Your Famous Chinese Account Shopping Help Famous Chinese Homepage China Chinese Chinese Culture Chinese Restaurant & Chinese Food Travel to China Chinese Economy & Chinese Trade Chinese Medicine & Chinese Herb Chinese Art
logo
Search
March 8, 2014
Table of Contents
1 Introduction
Chinese remainder theorem

Wikipedia

 
The Chinese remainder theorem is any of a number of related results in abstract algebra and number theory.




The original form of the theorem, contained in a book by the Chinese mathematician Qin Jiushao published in 1247, is a statement about simultaneous congruences (see modular arithmetic). Suppose n<sub>1</sub>, ..., n<sub>k</sub> are positive integer|integers which are pairwise coprime (meaning greatest common divisor|gcd
(n<sub>i</sub>, n<sub>j</sub>) = 1 whenever i &ne; j). Then, for any given integers a<sub>1</sub>, ..., a<sub>k</sub>, there exists an integer x solving the system of simultaneous congruences

<math>x \equiv a_i \pmodn_i \quad\mathrmfor\; i = 1, \cdots, k.</math>


Furthermore, all solutions x to this system are congruent modulo the product n = n<sub>1</sub>...n<sub>k</sub>.

A solution x can be found as follows. For each i; the integers n<sub>i</sub> and n/n<sub>i</sub> are coprime, and using the extended Euclidean algorithm we can find integers r and s such that r n<sub>i</sub> + s n/n<sub>i</sub> = 1. If we set e<sub>i</sub> = s n/n<sub>i</sub>, then we have

<math>e_i \equiv 1 \pmodn_i \quad\mathrmand\quad

e_i \equiv 0 \pmodn_j</math>

for j &ne; i.

The solution to the system of simultaneous congruences is therefore

<math> x = \sum_i=1..k a_i e_i.\ </math>


For example, consider the problem of finding an integer x such that

<math>x \equiv 2 \pmod3 </math>

<math>x \equiv 3 \pmod4 </math>

<math>x \equiv 2 \pmod5. </math>


Using the extended Euclidean algorithm for 3 and 4&times;5 = 20, we find (-13) &times; 3 + 2 &times; 20 = 1, i.e. e<sub>1</sub> = 40. Using the Euclidean algorithm for 4 and 3&times;5 = 15, we get (-11) &times; 4 + 3 &times; 15 = 1. Hence, e<sub>2</sub> = 45. Finally, using the Euclidean algorithm for 5 and 3&times;4 = 12, we get 5 &times; 5 + (-2) &times; 12 = 1, meaning e<sub>3</sub> = -24. A solution x is therefore 2 &times; 40 + 3 &times; 45 + 2 &times; (-24) = 167. All other solutions are congruent to 167 modulo 60, which means that they are all congruent to 47 modulo 60.

Sometimes, the simultaneous congruences can be solved even if the <i>n<sub>i</sub></i>'s are not pairwise coprime. The precise criterion is as follows: a solution x exists if and only if a<sub>i</sub> &equiv; a<sub>j</sub> (mod gcd(n<sub>i</sub>, n<sub>j</sub>)) for all i and j. All solutions x are congruent modulo the least common multiple of the n<sub>i</sub>.

Using the method of successive substitution can often yield solutions to simultaneous congruences, even when the moduli are not pairwise coprime.




For a principal ideal domain R the Chinese remainder theorem takes the following form: If u<sub>1</sub>, ..., u<sub>k</sub> are elements of R which are pairwise coprime, and u denotes the product u<sub>1</sub>...u<sub>k</sub>, then the ring R/uR and the product of rings|product ring R/u<sub>1</sub>R x ... x R/u<sub>k</sub>R are isomorphic via the ring homomorphism|isomorphism

<math>f : R/uR \rightarrow R/u_1R \times \cdots \times

R/u_k R </math>

such that

<math>x \;\mathrmmod\,uR \rightarrow (x \;\mathrmmod\,u_1R) \times \cdots \times

(x \;\mathrmmod\,u_kR). </math>

The inverse isomorphism can be constructed as follows. For each i, the elements u<sub>i</sub> and u/u<sub>i</sub> are coprime, and therefore there exist elements r and s in R with

<math>r u_i + s u/u_i = 1. </math>


Set e<sub>i</sub> = s u/u<sub>i</sub>. Then the inverse is the map

<math>g : R/u_1R \times \cdots \times R/u_kR

\rightarrow R/uR </math>

such that

<math>(a_1 \;\mathrmmod\,u_1R) \times \cdots \times (a_k \;\mathrmmodu_kR) \rightarrow

\sum_i=1..k a_i e_i \pmoduR. </math>




One of the most general forms of the Chinese remainder theorem can be formulated for ring (algebra)|rings and (two-sided) ring ideal|ideals. If R is a ring and I<sub>1</sub>, ..., I<sub>k</sub> are ideals of R which are pairwise coprime (meaning that I<sub>i</sub> + I<sub>j</sub> = R whenever i &ne; j), then the product I of these ideals is equal to their intersection, and the ring R/I is isomorphic to the product of rings|product ring R/I<sub>1</sub> x R/I<sub>2</sub> x ... x R/I<sub>k</sub> via the ring homomorphism|isomorphism

<math>f : R/I \rightarrow R/I_1 \times \cdots \times R/I_k </math>


such that

<math>x \;\mathrmmod\,I \rightarrow (x \;\mathrmmod\,I_1) \times \cdots \times

(x \;\mathrmmod I_k).</math>



  • http://www.cut-the-knot.org/blue/chinese.shtml Chinese remainder theorem


Category:Modular arithmeticCategory:Commutative algebraCategory:Theorems

de:Chinesischer Restsatz
nl:Chinese reststelling
ja:中国の剰余定理
pl:Chińskie twierdzenie o resztach
sv:Kinesiska restsatsen
zh:中国剩余定理

This article is licensed under the GNU Free Documentation License. It uses material from the Wikipedia article "Chinese remainder theorem".


Last Modified:   2005-04-13


Search
All informatin on the site is © FamousChinese.com 2002-2005. Last revised: January 2, 2004
Are you interested in our site or/and want to use our information? please read how to contact us and our copyrights.
To post your business in our web site? please click here. To send any comments to us, please use the Feedback.
To let us provide you with high quality information, you can help us by making a more or less donation: