Mathematics for Computer Science

8.9. What has SAT got to do with it? 223

(b)For any positive integer,k, letkbe the integers inŒ1;k/that are relatively
prime tok. Prove that the functionf from part (a) also defines a bijection from
.ab/toab.

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

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

(d)Prove Corollary 8.7.7: for any numbern > 0, 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.19.
The general version of the Chinese Remainder theorem (Problem 8.17) extends to
more than two relatively prime moduli. Namely,

Theorem(General Chinese Remainder).Supposea 1 ;:::;akare integers greater
than 1 and each is relatively prime to the others. LetnWWDa 1
a 2


ak. Then for
any integersm 1 ;m 2 ;:::;mk, there is a uniquex 2 Œ0;n/such that

xmi .modai/;

for 1 ik.

The proof is a routine induction onkusing a fact that follows immediately from
unique factorization: if a number is relatively prime to some other numbers, then it
is relatively prime to their product.
Now suppose ann-bit number,N, was a product of relatively primek-bit num-
bers, wherenwas big, butkwas small enough to be handled by cheap and available
arithmetic hardware units. Suppose a calculation requiring a large number of addi-
tions and multiplications moduloNhad to be performed starting with some small
set ofn-bit numbers. For example, suppose we wanted to compute

rem. .x3/^110033 ..yC7/^27123 z^4328 / ;N/

which would require several dozenn-bit operations starting from the three numbers
x;y;z.
Doing a multiplication or addition moduloN directly requires breaking up the
n-bit numbersx;y;zand all the intermediate results of the modNcalculation into