Page 298 - Discrete Mathematics and Its Applications

4.4 Solving Congruences 277

Once we have an inverse a of a modulo m, we can solve the congruence ax ≡ b(mod m)
by multiplying both sides of the linear congruence by a, as Example 3 illustrates.

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
of the congruence by −2 shows that

−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 ≡
6 (mod 7).
We need to determine whether every x with x ≡ 6 (mod 7) is a solution. Assume that
x ≡ 6 (mod 7). Then, by Theorem 5 of Section 4.1, it follows that

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,.... ▲

The Chinese Remainder Theorem

Systems of linear congruences arise in many contexts. For example, as we will see later, they are
the basis for a method that can be used to perform arithmetic with large integers. Such systems
can even be found as word puzzles in the writings of ancient Chinese and Hindu mathematicians,
such as that given in Example 4.

EXAMPLE 4 In the first century, the Chinese mathematician Sun-Tsu asked:

There are certain things whose number is unknown. When divided by 3, the remainder
is 2; when divided by 5, the remainder is 3; and when divided by 7, the remainder is 2. What
will be the number of things?

This puzzle can be translated into the following question: What are the solutions of the
systems of congruences

x ≡ 2 (mod 3),
x ≡ 3 (mod 5),
x ≡ 2 (mod 7)?

We will solve this system, and with it Sun-Tsu’s puzzle, later in this section. ▲

The Chinese remainder theorem, named after the Chinese heritage of problems involving
systems of linear congruences, states that when the moduli of a system of linear congruences
are pairwise relatively prime, there is a unique solution of the system modulo the product of the
moduli.