**Theorem 6.8.1** (Chinese Remainder Theorem)
Assume

are coprime and let

. Then

satisfying simultaneously

and

. Moreover the solution is unique up to
congruence modulo

.

*Proof*.
If

,

then

and there is a
unique solution of

with

and

.

is the inverse of

modulo

. Observe that

iff

, iff

, which gives
that

or

. Therefore the elements in

pair off so that

and the theorem is proved.