Page 297 - Discrete Mathematics and Its Applications

276 4 / Number Theory and Cryptography

EXAMPLE 1 Find an inverse of 3 modulo 7 by first finding Bézout coefficients of 3 and 7. (Note that we have
already shown that 5 is an inverse of 3 modulo 7 by inspection.)

Solution: Because gcd(3, 7) = 1, Theorem 1 tells us that an inverse of 3 modulo 7 exists. The
Euclidean algorithm ends quickly when used to find the greatest common divisor of 3 and 7:

7 = 2 · 3 + 1.

From this equation we see that

−2 · 3 + 1 · 7 = 1.

This shows that −2 and 1 are Bézout coefficients of 3 and 7. We see that −2 is an inverse of 3
modulo 7. Note that every integer congruent to −2 modulo 7 is also an inverse of 3, such as 5,
−9, 12, and so on. ▲

EXAMPLE 2 Find an inverse of 101 modulo 4620.

Solution: For completeness, we present all steps used to compute an inverse of 101 modulo 4620.
(Only the last step goes beyond methods developed in Section 4.3 and illustrated in Example 17
in that section.) First, we use the Euclidean algorithm to show that gcd(101, 4620) = 1. Then
we will reverse the steps to find Bézout coefficients a and b such that 101a + 4620b = 1. It will
then follow that a is an inverse of 101 modulo 4620. The steps used by the Euclidean algorithm
to find gcd(101, 4620) are

4620 = 45 · 101 + 75

101 = 1 · 75 + 26
75 = 2 · 26 + 23
26 = 1 · 23 + 3
23 = 7 · 3 + 2
3 = 1 · 2 + 1

2 = 2 · 1.

Because the last nonzero remainder is 1, we know that gcd(101, 4620) = 1. We can now find
the Bézout coefficients for 101 and 4620 by working backwards through these steps, expressing
gcd(101, 4620) = 1 in terms of each successive pair of remainders. In each step we eliminate
the remainder by expressing it as a linear combination of the divisor and the dividend. We obtain

1 = 3 − 1 · 2

= 3 − 1 · (23 − 7 · 3) =−1 · 23 + 8 · 3
=−1 · 23 + 8 · (26 − 1 · 23) = 8 · 26 − 9 · 23
= 8 · 26 − 9 · (75 − 2 · 26) =−9 · 75 + 26 · 26
=−9 · 75 + 26 · (101 − 1 · 75) = 26 · 101 − 35 · 75
= 26 · 101 − 35 · (4620 − 45 · 101) =−35 · 4620 + 1601 · 101.

That −35 · 4620 + 1601 · 101 = 1 tells us that −35 and 1601 are Bézout coefficients of 4620
and 101, and 1601 is an inverse of 101 modulo 4620. ▲