Mathematics for Computer Science

8.13. References 305

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

.ab/D.a/.b/:

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

(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.

(b)For any positive integer,k, letZkbe the integers inŒ0::k/that are relatively
prime tok. Prove that the functionf from part (a) also defines a bijection from
ZabtoZaZb.

(c)Conclude from the preceding parts of this problem that

.ab/D.a/.b/: (8.44)

(d)Prove Corollary 8.10.11: for any numbern > 1, ifp 1 ,p 2 ,... ,pj are the
(distinct) prime factors ofn, then

.n/Dn



1

1

p 1



1

1

p 2





1

1

pj



:

Problem 8.63.

Definition.Define theorderofkoverZnto be

ord.k;n/WWDminfm > 0jkmD1 .Zn/g:

If no positive power ofkequals 1 inZn, then ord.k;n/WWD1.

(a)Show thatk 2 Zniffkhas finite order inZn.

(b)Prove that for everyk 2 Zn, the order ofkoverZndivides.n/.

Hint:LetmDord.k;n/. Consider the quotient and remainder of.n/divided by
m.