Mathematics for Computer Science

Chapter 8 Number Theory222

theChinese Remainder Theorem, which says that for allm;n, there is anxsuch
that

xmmoda; (8.16)

xn modb: (8.17)

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

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)?

Homework Problems

Problem 8.18.
Supposea;bare relatively prime integers greater than 1. In this problem you will
prove that Euler’s function ismultiplicative, namely, that

.ab/D.a/.b/:

The proof is an easy consequence of the Chinese Remainder Theorem (Problem 8.17).

(a)Conclude from the Chinese Remainder Theorem that the functionfWŒ0;ab/!
Œ0;a/Œ0;b/defined by

f.x/WWD.rem.x;a/;rem.x;b//

is a bijection.