292 4 / Number Theory and Cryptography

Using inspection to find an inverse of a modulo m is easy when m is small. To find this
inverse, we look for a multiple of a that exceeds a multiple of m by 1. For example, to find an
inverse of 3 modulo 7, we can find j ⋅ 3 for j = 1, 2, … , 6, stopping when we find a multiple of
3 that is one more than a multiple of 7. We can speed this approach up if we note that 2 ⋅ 3 ≡
!1 (mod 7). This means that (!2) ⋅ 3 ≡ 1 (mod 7). Hence, 5 ⋅ 3 ≡ 1 (mod 7), so 5 is an inverse
of 3 modulo 7.
We can design a more e!cient algorithm than brute force to find an inverse of a modulo m
when gcd(a, m) = 1 using the steps of the Euclidean algorithm. By reversing these steps as
in Example 17 of Section 4.3, we can find a linear combination sa + tm = 1, where s and t
are integers. Reducing both sides of this equation modulo m tells us that s is an inverse of
a modulo m. We illustrate this procedure in Example 1.

EXAMPLE 1 Find an inverse of 3 modulo 7 by first finding Bézout coe!cients 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 coe!cients 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 coe!cients 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 coe!cients for 101 and 4620 by working backwards through these steps, expressing
 4.4 Solving Congruences 293

gcd(101, 4620) = 1 in terms of each successive pair of remainders. In each step we elimi-
nate 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 coe!cients of 4620
and 101, and 1601 is an inverse of 101 modulo 4620. ◂

Once we have an inverse a of a modulo m, we can solve the congruence ax ≡ b (mod m)

EXAMPLE 3 What are the solutions of the linear congruence 3x ≡ 4 (mod 7)?

Solution: By Example 1 we know that !2 is an inverse of 3 modulo 7. Multiplying both sides

!2 ⋅ 3x ≡ !2 ⋅ 4 (mod 7).

Because !6 ≡ 1 (mod 7) and !8 ≡ 6 (mod 7), it follows that if x is a solution, then x ≡ !8 ≡

3x ≡ 3 ⋅ 6 = 18 ≡ 4 (mod 7),

which shows that all such x satisfy the congruence. We conclude that the solutions to the
congruence are the integers x such that x ≡ 6 (mod 7), namely, 6, 13, 20, … and !1, !8,
!15, … . ◂
 4.4 Solving Congruences 301

Exercises

1. Show that 15 is an inverse of 7 modulo 26. ∗ 15. Show that if m is an integer greater than 1 and ac ≡
2. Show that 937 is an inverse of 13 modulo 2436. bc (mod m), then a ≡ b (mod m!gcd(c, m)).
3. By inspection (as discussed prior to Example 1), find an 16. a) Show that the positive integers less than 11, except
inverse of 4 modulo 9. 1 and 10, can be split into pairs of integers such that
4. By inspection (as discussed prior to Example 1), find an each pair consists of integers that are inverses of each
inverse of 2 modulo 17. other modulo 11.
5. Find an inverse of a modulo m for each of these pairs b) Use part (a) to show that 10! ≡ −1 (mod 11).
of relatively prime integers using the method followed in 17. Show that if p is prime, the only solutions of x2 ≡
Example 2. 1 (mod p) are integers x such that x ≡ 1 (mod p) or x ≡ −1
a) a = 4, m = 9 (mod p).
b) a = 19, m = 141
∗ 18. a) Generalize the result in part (a) of Exercise 16; that
c) a = 55, m = 89
d) a = 89, m = 232 is, show that if p is a prime, the positive integers less
6. Find an inverse of a modulo m for each of these pairs than p, except 1 and p − 1, can be split into (p − 3)!2
of relatively prime integers using the method followed in pairs of integers such that each pair consists of inte-
Example 2. gers that are inverses of each other. [Hint: Use the
result of Exercise 17.]
b) From part (a) conclude that (p − 1)! ≡ −1 (mod p)
a) a = 2, m = 17
b) a = 34, m = 89
c) a = 144, m = 233 whenever p is prime. This result is known as Wilson’s
d) a = 200, m = 1001 theorem.
∗ 7. Show that if a and m are relatively prime positive inte- c) What can we conclude if n is a positive integer such
gers, then the inverse of a modulo m is unique modulo that (n − 1)! ≢ −1 (mod n)?
m. [Hint: Assume that there are two solutions b and c of ∗ 19. This exercise outlines a proof of Fermat’s little theorem.
the congruence ax ≡ 1 (mod m). Use Theorem 7 of Sec- a) Suppose that a is not divisible by the prime p. Show
tion 4.3 to show that b ≡ c (mod m).] that no two of the integers 1 ⋅ a, 2 ⋅ a, … , (p − 1)a are
8. Show that an inverse of a modulo m, where a is an in- congruent modulo p.
teger and m > 2 is a positive integer, does not exist if b) Conclude from part (a) that the product of
gcd(a, m) > 1. 1, 2, … , p − 1 is congruent modulo p to the product
9. Solve the congruence 4x ≡ 5 (mod 9) using the inverse of a, 2a, … , (p − 1)a. Use this to show that
of 4 modulo 9 found in part (a) of Exercise 5.
10. Solve the congruence 2x ≡ 7 (mod 17) using the inverse (p − 1)! ≡ ap−1 (p − 1)! (mod p).
of 2 modulo 17 found in part (a) of Exercise 6.
11. Solve each of these congruences using the modular in-
c) Use Theorem 7 of Section 4.3 to show from part (b)
that ap−1 ≡ 1 (mod p) if p ̸ ∣ a. [Hint: Use Lemma 3
verses found in parts (b), (c), and (d) of Exercise 5.
a) 19x ≡ 4 (mod 141) of Section 4.3 to show that p does not divide (p − 1)!
b) 55x ≡ 34 (mod 89)
c) 89x ≡ 2 (mod 232)
and then use Theorem 7 of Section 4.3. Alternatively,
use Wilson’s theorem from Exercise 18(b).]
12. Solve each of these congruences using the modular in-
verses found in parts (b), (c), and (d) of Exercise 6. d) Use part (c) to show that ap ≡ a (mod p) for all inte-
a) 34x ≡ 77 (mod 89)
gers a.
b) 144x ≡ 4 (mod 233) 20. Use the construction in the proof of the Chinese remain-
c) 200x ≡ 13 (mod 1001) der theorem to find all solutions to the system of congru-
13. Find the solutions of the congruence 15x2 + 19x ≡ 5 ences x ≡ 2 (mod 3), x ≡ 1 (mod 4), and x ≡ 3 (mod 5).
(mod 11). [Hint: Show the congruence is equivalent to 21. Use the construction in the proof of the Chinese remain-
the congruence 15x2 + 19x + 6 ≡ 0 (mod 11). Factor the der theorem to find all solutions to the system of congru-
left-hand side of the congruence; show that a solution of ences x ≡ 1 (mod 2), x ≡ 2 (mod 3), x ≡ 3 (mod 5), and
the quadratic congruence is a solution of one of the two x ≡ 4 (mod 11).
di!erent linear congruences.] 22. Solve the system of congruence x ≡ 3 (mod 6) and
14. Find the solutions of the congruence 12x2 + 25x ≡ x ≡ 4 (mod 7) using the method of back substitution.
10 (mod 11). [Hint: Show the congruence is equivalence
to the congruence 12x2 + 25x + 12 ≡ 0 (mod 11). Factor 23. Solve the system of congruences in Exercise 20 using the
the left-hand side of the congruence; show that a solu- method of back substitution.
tion of the quadratic congruence is a solution of one of 24. Solve the system of congruences in Exercise 21 using the
two di!erent linear congruences.] method of back substitution.