Chinese Remainder Theorem Article Index for
Chinese 		Website Links For
Chinese 		 

Information About

Chinese Remainder Theorem
  CATEGORIES ABOUT CHINESE REMAINDER THEOREM
   
modular arithmetic
   
commutative algebra
   
mathematical theorems
   
SHOPPER'S DELIGHT
 
Shop For:  
Department
Price Minimum:
Price Maximum:
      




SIMULTANEOUS CONGRUENCES OF INTEGERS


The original form of the theorem, contained in a Third-century book by Chinese mathematician Sun Tzu and later republished in a 1247 book by Qin Jiushao , is a statement about simultaneous congruences (see Modular Arithmetic ). Suppose ''n''1, ..., ''n''''k'' are Integers which are Pairwise Coprime (meaning Gcd
(''n''''i'', ''n''''j'') = 1 whenever ''i'' ≠ ''j''). Then, for any given integers ''a''1, ..., ''a''''k'', there exists an integer ''x'' solving the system of simultaneous congruences

:x \equiv a_i \pmod{n_i} \quad\mathrm{for}\; i = 1, \ldots, k.

Furthermore, all solutions ''x'' to this system are congruent modulo the product ''n'' = ''n''1...''n''''k''.

A solution ''x'' can be found as follows. For each ''i'' the integers ''ni'' and ''n''/''ni'' are coprime, and using the Extended Euclidean Algorithm we can find integers ''r'' and ''s'' such that ''r ni'' + ''s'' ''n''/''ni'' = 1. If we set ''ei'' = ''s'' ''n''/''ni'', then we have

:e_i \equiv 1 \pmod{n_i} \quad\mathrm{and}\quad
e_i \equiv 0 \pmod{n_j}

for ''j'' ≠ ''i''.

One solution to the system of simultaneous congruences is therefore

: x = \sum_{i=1}^k a_i e_i.\

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

:x \equiv 2 \pmod{3},
:x \equiv 3 \pmod{4},
:x \equiv 2 \pmod{5}.

Using the Extended Euclidean Algorithm for 3 and 4×5 = 20, we find (-13) × 3 + 2 × 20 = 1, i.e. ''e''1 = 40. Using the Euclidean algorithm for 4 and 3×5 = 15, we get (-11) × 4 + 3 × 15 = 1. Hence, ''e''2 = 45. Finally, using the Euclidean algorithm for 5 and 3×4 = 12, we get 5 × 5 + (-2) × 12 = 1, meaning ''e''3 = -24. A solution ''x'' is therefore 2 × 40 + 3 × 45 + 2 × (-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 ni's are not pairwise coprime. The precise criterion is as follows: a solution ''x'' exists if and only if ''ai'' ≡ ''aj'' (mod gcd(''ni'', ''nj'')) for all ''i'' and ''j''. All solutions ''x'' are congruent modulo the Least Common Multiple of the ''ni''.

The Method Of Successive Substitution can often yield solutions to simultaneous congruences, even when the moduli are not pairwise coprime.


STATEMENT FOR PRINCIPAL IDEAL DOMAINS


For a , and ''u'' denotes the product ''u''1...''uk'', then the Quotient Ring ''R/uR'' and the Product Ring ''R/u''1''R'' x ... x ''R/ukR'' are isomorphic via the Isomorphism

:f : R/uR ightarrow R/u_1R imes \cdots imes
R/u_k R

such that

:f(x +uR) = (x + u_1R, \ldots , x +u_kR) \quad\mbox{ for every } x\in R.

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

:r u_i + s u/u_i = 1.

Set ''ei'' = ''s u/ui''. Then the inverse of ''f'' is the map

:g : R/u_1R imes \cdots imes R/u_kR
ightarrow R/uR

such that

:g(a_1+u_1R,\ldots ,a_k+u_kR)=
\left( \sum_{i=1}^k a_i e_i ight) + uR \quad\mbox{ for all }a_1,\ldots,a_k\in R.

Note that this statement is a straightforward generalization of the above theorem about integer congruences: the ring Z of Integer s is a principal ideal domain, the Surjectivity of the map ''f'' shows that every system of congruences of the form
:x \equiv a_i \pmod{u_i} \quad\mathrm{for}\; i = 1, \ldots, k
can be solved for ''x'', and the Injectivity of the map ''f'' shows that all the solutions ''x'' are congruent modulo ''u''.


STATEMENT FOR GENERAL RINGS


The general form of the Chinese remainder theorem, which implies all the statements given above, can be formulated for Rings and (two-sided) Ideals . If ''R'' is a ring and ''I''1, ..., ''Ik'' are two-sided ideals of ''R'' which are pairwise Coprime (meaning that ''Ii'' + ''Ij'' = ''R'' whenever ''i'' ≠ ''j''), then the product ''I'' of these ideals is equal to their intersection, and the Quotient Ring ''R/I'' is isomorphic to the Product Ring ''R''/''I''1 x ''R''/''I''2 x ... x ''R''/''I''''k'' via the Isomorphism

:f : R/I ightarrow R/I_1 imes \cdots imes R/I_k

such that

:f(x + I) = (x +I_1, \ldots , x+I_k) \quad\mbox{ for all } x\in R.


APPLICATIONS

In the RSA Algorithm calculations are made modulo n, where n is a product of two primes p and q. Common sizes for n are 1024, 2048 or 4096 Bit s, making calculations very time-consuming. Using Chinese remaindering these calculations can be transported from the ring \Bbb{Z}_n to the ring \Bbb{Z}_p imes \Bbb{Z}_q. The sum of the bit sizes of p and q is the bit size of n, making p and q considerably smaller than n. This greatly simplifies calculations.

Another potential application of Chinese remainder theorem is for counting soldiers in an army. Via Chinese remainder theorem, the general has the soldiers quickly line up in groups of 2, 3, 5, 7, 11, and so on and counts the remaining soldiers that can't make complete groups. After enough of these tests are made, the general can quickly calculate how many soldiers he has exactly; thus he has done a 3 hour headcount in all of 2 minutes. This fact, that a large number can be represented by a small number of relatively small remainders, is also the core idea of Residue Number System s.


SEE ALSO



EXTERNAL LINKS



REFERENCES