Mathematics for Computer Science

8.13. References 303

Problem 8.58.
Supposea;bare relatively prime and greater than 1. In this problem you will prove
theChinese Remainder Theorem, which says that for allm;n, there is anxsuch
that

xmmoda; (8.42)

xn modb: (8.43)

Moreover,xis unique up to congruence moduloab, namely, ifx^0 also satis-
fies (8.42) and (8.43), then
x^0 xmodab:
(a)Prove that for anym;n, there is somexsatisfying (8.42) and (8.43).

Hint: Letb^1 be an inverse ofbmoduloaand defineeaWWDb^1 b. Defineeb
similarly. LetxDmeaCneb.

(b)Prove that

Œx 0 modaAND x 0 modbç implies x 0 modab:

(c)Conclude that



xx^0 modaAND xx^0 modb



implies xx^0 modab:

(d)Conclude that the Chinese Remainder Theorem is true.

(e)What about the converse of the implication in part (c)?

Problem 8.59.
LetSkD 1 kC 2 kC:::C.p1/k, wherepis an odd prime andkis a positive
multiple ofp 1. Use Fermat’s theorem to prove thatSk1 .modp/.

Problem 8.60.

(a)Prove that

kmD1 .Zn/ IMPLIES ord.k;n/jm:

Hint: Take the remainder ofmdivided by the order. Reminder: Theorderof
k 2 Znis the smallest positivemsuch thatkmD1 .Zn/.