Page 300 - Discrete Mathematics and Its Applications

4.4 Solving Congruences 279

It follows that 23 is the smallest positive integer that is a simultaneous solution.We conclude that
23 is the smallest positive integer that leaves a remainder of 2 when divided by 3, a remainder
of 3 when divided by 5, and a remainder of 2 when divided by 7. ▲

Although the construction in Theorem 2 provides a general method for solving systems of
linear congruences with pairwise relatively prime moduli, it can be easier to solve a system using
a different method. Example 6 illustrates the use of a method known as back substitution.
EXAMPLE 6 Use the method of back substitution to find all integers x such that x ≡ 1 (mod 5),
x ≡ 2 (mod 6), and x ≡ 3 (mod 7).

Solution: By Theorem 4 in Section 4.1, the first congruence can be rewritten as an equality,
x = 5t + 1 where t is an integer. Substituting this expression for x into the second congruence
tells us that

5t + 1 ≡ 2 (mod 6),

which can be easily solved to show that t ≡ 5 (mod 6) (as the reader should verify). Using
Theorem 4 in Section 4.1 again, we see that t = 6u + 5 where u is an integer. Substituting this
expression for t back into the equation x = 5t + 1 tells us that x = 5(6u + 5) + 1 = 30u + 26.
We insert this into the third equation to obtain

30u + 26 ≡ 3 (mod 7).

Solving this congruence tells us that u ≡ 6 (mod 7) (as the reader should verify). Hence, Theo-
rem 4 in Section 4.1 tells us that u = 7v + 6 where v is an integer. Substituting this expression
for u into the equation x = 30u + 26 tells us that x = 30(7v + 6) + 26 = 210u + 206. Trans-
lating this back into a congruence, we find the solution to the simultaneous congruences,

x ≡ 206 (mod 210). ▲

Computer Arithmetic with Large Integers

Suppose that m 1 ,m 2 ,...,m n are pairwise relatively prime moduli and let m be their product.
By the Chinese remainder theorem, we can show (see Exercise 28) that an integer a with
0 ≤ a< m can be uniquely represented by the n-tuple consisting of its remainders upon division
by m i ,i = 1, 2,...,n. That is, we can uniquely represent a by

(a mod m 1 ,a mod m 2 ,...,a mod m n ).

EXAMPLE 7 What are the pairs used to represent the nonnegative integers less than 12 when they are rep-
resented by the ordered pair where the first component is the remainder of the integer upon
division by 3 and the second component is the remainder of the integer upon division by 4?

Solution: We have the following representations, obtained by finding the remainder of each
integer when it is divided by 3 and by 4:

0 = (0, 0) 4 = (1, 0) 8 = (2, 0)
1 = (1, 1) 5 = (2, 1) 9 = (0, 1)
2 = (2, 2) 6 = (0, 2) 10 = (1, 2)
▲
3 = (0, 3) 7 = (1, 3) 11 = (2, 3).