Mathematics for Computer Science

Chapter 8 Number Theory278

8.10.1 Computing Euler’sFunction

RSA works using arithmetic modulo the product of two large primes, so we begin
with an elementary explanation of how to compute.pq/for primespandq:

Lemma 8.10.9.
.pq/D.p1/.q1/

for primesp¤q.

Proof. Sincepandqare prime, any number that is not relatively prime topqmust
be a multiple ofpor a multiple ofq. Among thepqnumbers inŒ0::pq/, there are
preciselyqmultiples ofpandpmultiples ofq. Sincepandqare relatively prime,
the only number inŒ0::pq/that is a multiple of bothpandqis 0. Hence, there are
pCq 1 numbers inŒ0::pq/that arenotrelatively prime ton. This means that

.pq/Dpq.pCq1/

D.p1/.q1/;

as claimed.^14 

The following theorem provides a way to calculate.n/for arbitraryn.

Theorem 8.10.10.

(a) Ifpis a prime, then.pk/Dpkpk^1 fork 1.
(b) Ifaandbare relatively prime, then.ab/D.a/.b/.
Here’s an example of using Theorem 8.10.10 to compute.300/:
.300/D.2^2
3
52 /
D.2^2 /
.3/
.5^2 / (by Theorem 8.10.10.(b))
D.2^2 21 /.3^1 30 /.5^2 51 / (by Theorem 8.10.10.(a))
D80:
Note that Lemma 8.10.9 also follows as a special case of Theorem 8.10.10.(b),
since we know that.p/Dp 1 for any prime,p.
To prove Theorem 8.10.10.(a), notice that everypth number among thepknum-
bers inŒ0::pk/is divisible byp, and only these are divisible byp. So1=pof these
numbers are divisible bypand the remaining ones are not. That is,

.pk/Dpk.1=p/pkDpkpk^1 :

We’ll leave a proof of Theorem 8.10.10.(b) to Problem 8.62.
As a consequence of Theorem 8.10.10, we have

(^14) This proof previews a kind of counting argument that we will explore more fully in Part III.