Page 296 - Discrete Mathematics and Its Applications

4.4 Solving Congruences 275

Linear Congruences

A congruence of the form

ax ≡ b(mod m),

where m is a positive integer, a and b are integers, and x is a variable, is called a linear
congruence. Such congruences arise throughout number theory and its applications.
How can we solve the linear congruence ax ≡ b(mod m), that is, how can we find all
integers x that satisfy this congruence? One method that we will describe uses an integer a
such that aa ≡ 1 (mod m), if such an integer exists. Such an integer a is said to be an inverse
of a modulo m. Theorem 1 guarantees that an inverse of a modulo m exists whenever a and m
are relatively prime.

THEOREM 1 If a and m are relatively prime integers and m> 1, then an inverse of a modulo m exists.
Furthermore, this inverse is unique modulo m. (That is, there is a unique positive integer a
less than m that is an inverse of a modulo m and every other inverse of a modulo m is
congruent to a modulo m.)

Proof: By Theorem 6 of Section 4.3, because gcd(a, m) = 1, there are integers s and t such
that

sa + tm = 1.

This implies that

sa + tm ≡ 1 (mod m).

Because tm ≡ 0 (mod m), it follows that

sa ≡ 1 (mod m).

Consequently, s is an inverse of a modulo m. That this inverse is unique modulo m is left as
Exercise 7.

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 efficient 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.