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.p 1/k, wherepis an odd prime andkis a positive
multiple ofp 1. Use Fermat’s theorem to prove thatSk 1 .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/.