Mathematics for Computer Science

Chapter 14 Cardinality Rules586

Rule(Inclusion-Exclusion-II).
ˇˇ
ˇˇ
ˇ

[n

iD 1

Si

ˇˇ

ˇˇ

ˇ

D

X

;¤If1;:::;ng

.1/jIjC^1

ˇˇ

ˇˇ

ˇ

\

i 2 I

Si

ˇˇ

ˇˇ

ˇ

(14.6)

A proof of these rules using just highschool algebra is given in Problem 14.52.

14.9.5 Computing Euler’s Function

We can also use Inclusion-Exclusion to derive the explicit formula for Euler’s func-
tion claimed in Corollary 8.10.11: if the prime factorization ofnisp 1 e^1


pemmfor
distinct primespi, then

.n/Dn

Ym

iD 1



1

1

pi



: (14.7)

To begin, letSbe the set of integers inŒ0::n/that arenotrelatively prime ton.
So.n/DnjSj. Next, letCabe the set of integers inŒ0::n/that are divisible by
a:
CaWWDfk 2 Œ0::n/j ajkg:

So the integers inSare precisely the integers inŒ0::n/that are divisible by at least
one of thepi’s. Namely,

SD

[m

iD 1

Cpi: (14.8)

We’ll be able to find the size of this union using Inclusion-Exclusion because the
intersections of theCpi’s are easy to count. For example,Cp\Cq\Cris the set
of integers inŒ0::n/that are divisible by each ofp,qandr. But since thep;q;r
are distinct primes, being divisible by each of them is the same as being divisible
by their product. Now ifkis a positive divisor ofn, then there are exactlyn=k
multiples ofkinŒ0::n/. So exactlyn=pqrof the integers inŒ0::n/are divisible by
all three primesp,q,r. In other words,

jCp\Cq\CrjD

n

pqr

:

This reasoning extends to arbitrary intersections ofCp’s, namely,
ˇ
ˇˇ
ˇˇ
ˇ

\

j 2 I

Cpj

ˇ

ˇˇ

ˇˇ

ˇ

D

n

Q

j 2 Ipj

; (14.9)