Mathematics for Computer Science

8.7. Arithmetic with an Arbitrary Modulus 213

mirrors the proof of Fermat’s Theorem. In particular,

k 1 
k 2 


kr

Drem.k 1 
k;n/
rem.k 2 
k;n/


rem.kr
k;n/ (by Lemma 8.7.3)

.k 1 
k/
.k 2 
k/



.kr
k/ .modn/ (by Cor 8.5.3)

.k 1 
k 2 


kr/
kr .modn/ (rearranging terms)

By Lemma 8.7.2, each of the termskican be cancelled, proving the claim. 

We can find multiplicative inverses using Euler’s theorem as we did with Fer-
mat’s theorem: ifkis relatively prime ton, thenk.n/^1 is a multiplicative inverse
ofkmodulon. However, this approach requires computing.n/. In the next sec-
tion, we’ll show that computing.n/is easyifwe know the prime factorization
ofn. Unfortunately, finding the factors ofncan be hard to do whennis large, and
so the Pulverizer is generally the best approach to computing inverses modulon.

8.7.3 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.7.5.
.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.^6 

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

Theorem 8.7.6.

(^6) This proof provides a brief preview of the kinds of counting arguments that we will explore more
fully in Part III.