**We start with the elementary case of the
Chinese Remaindering Theorem
(Theorem 1).
Then we give a much more abstract version
(Theorem 2).
Then we state the Chinese Remaindering Theorem
and
the
Chinese Remaindering Algorithm
in the context of Euclidean domains.
**

(45) |

(47) |

Now assume that holds. This implies

Thus Relations (48) and (49) lead to

(50) |

Conversly

- implies that is divides and
- implies that is divides .

(51) |

- The kernel of is .
- If the tuple
has a pre-image
then we have
(52)

- is surjective iff for every such that we have .

(53) |

that is

(54) |

or

At this point of the proof we need the following lemma.

(56) |

(57) |

or equivalently

(58) |

Since these sets are non empty this implies

Since is an ideal we have and thus

(60) |

The lemma is proved.

**CONTINUING THEOREM'S **

(61) |

or equivalently

Relation (62) is a necessary condition for the existence of a pre-image of via the homomorphism . Therefore we proved the second statement of the theorem. Let us prove the third one.

Let us ssume first that is surjective. Let be such that . There exists such that

(63) |

Hence

(64) |

which implies . Conversly, let us assume that the ideals are pairwise coprime. Let be in the range and consider the product of all ideals except . It is a classical result that and are coprime. Let and such that . Observe that for all we have

(65) |

Now consider . Then

(66) |

satisfies

(67) |

This concludes the proof of the theorem.

(68) |

(69) |

(70) |

It is a well known fact that if the ideals are pairwise coprime ( for every with ) then their product is equal to their intersection [van91]. Therefore, we have the ring isomorphism of the statement. The group isomorphism follows from the previous ring isomorphism and the fact that the element

(71) |

is a unit iff every is a unit of .

**From now on
denotes an Euclidean domain.
**

(72) |

(73) |

- Every ideal of is generated by a single element. (That is, there exists an element such that is the set of the multiples of denoted by .)
- Two ideals and are coprime iff .

(74) |

Hence

and for with we have

The specification of Algorithm 4 follow easily from Relation (75) and (76).

(78) |

(79) |

(81) |

and thus

(82) |

Hence divides although holds. Therefore .

(83) |

**We reproduce below the ALDOR code for the Chinese Remaindering Algorithm.
More precisely, the operation interpolate satisfies exactly the
specification of Algorithm 4.
After the definition of the ChineseRemaindering domain
we prove that its operation combine satisifies the
specification of Algorithm 4
for the case of two moduli
and
.
The reader is left with the proof of the operation interpolate
which implements the general case (with
moduli).
**

ChineseRemaindering(E: EuclideanDomain): with { combine: (E, E) -> (E, E) -> E; interpolate: (List E, List E) -> E; } == add { combine(m1: E, m2: E): (E, E) -> E == { local u1: E; assert(m1 = unitCanonical m1); assert(m2 = unitCanonical m2); fn(r1: E, r2: E): E == { r1__new := r1 rem m1; r := (r2 - r1__new) rem m2 ; r := (r * u1) rem m2 ; r := r1__new + r * m1; } (u1, u2, g) := extendedEuclidean(m1, m2); fn } interpolate(lm: List E, lr: List E): E == { m := first lm; r := first lr rem m; for mi in rest lm for ri in rest lr repeat { r := combine(m, mi)(r, ri); m := m * mi; } return r; } }

According to Algorithm 4 the case of two moduli and requires the following computations

- := 0
- := extendedEuclidean( )
- := rem
- :=
- := extendedEuclidean( )
- := rem
- :=

- := extendedEuclidean( )
- := rem
- := rem
- :=

(84) |

we deduce the following congruences

(85) |

This last expression is exactly the quantity computed by

*
*

2008-01-07