Schaum's Outline of Discrete Mathematics, Third Edition (Schaum's Outlines)

296 PROPERTIES OF THE INTEGERS [CHAP. 11

Divide the equation and the modulusm=2295 byd=3 to obtain the congruence equation

364 x≡ 71 (mod 765) (11.12)

We know that 364 and 796 are relatively prime since we divided byd=gcd( 1092 , 2295 )=3; hence the equation

(11.12) has unique solution modulo 765. We solve (11.12) by first finding the solution of the equation

364 x≡ 1 (mod 765) (11.13)

This solution is obtained by findingsandtsuch that

364 s+ 765 t= 1

Using the Euclidean algorithm and “unraveling” as in Example 11.6 and Problem 11.21, we obtains=124 and

t=−59.

Accordingly,s=124 is the unique solution of (11.13). Multiplying this solutions=124 by 71 and reducing

modulo 765 we obtain

124 ( 71 )= 8804 ≡ 389 (mod 765)

This is the unique solution of(11.12).

Lastly, we add the new modulusm=765 to the solutionx 1 =389 two times to obtain the other two solutions of

the given equation:

x 2 = 389 + 765 = 1154 ,x 3 = 1154 + 765 = 1919

In other words,x 1 =389,x 2 =1154,x 3 =1919 form a complete set of solutions of the given congruence equation

1092 x≡213 (mod 2295).

11.55. Solve the congruence equation 455x≡204 (mod 469).

First use the Euclidean algorithm to findd=gcd( 455 , 469 )=7. Dividing 204 byd =7 yields 1 as a

remainder; that is, 7 does not divide 204. Thus the equation has no solution.

11.56. Find the smallest positive integerxsuch that whenxis divided by 3 it yields a remainder 2, whenxis

divided by 7 it yields a remainder 4, and whenxis divided by 10 it yields a remainder 6.

We seek the smallest positive common solution of the following three congruence equations:

(a) x≡ 2 (mod 3); (b) x≡ 4 (mod 7); (c) x≡ 6 (mod 10)

Observe that the moduli 3, 7, and 10 are pairwise relatively prime. (Moduli is the plural of modulus.) The

Chinese Remainder Theorem (CRT), Theorem 11.29, tells us that there is a unique solution modulo the product

m= 3 ( 7 )( 10 )=210. We solve the problems in two ways.

Method 1:First we apply CRT to the first two equations,

(a) x≡ 2 (mod 3) and (b) x≡ 4 (mod 7)

We know there is a unique solution moduloM= 3 ·7 = 21. Adding multiples of the modulusm=7 to the given

solutionx=4 of the second equation(b), we obtain the following three solutions of(b)which are less than 21:

4 , 11 , 18

Testing each of these solutions of(b)in the first equation(a), we find that 11 is the only solution of both equations.

Now we apply the same process to the two equations

(c) x≡ 6 (mod 10) and (d) x≡ 11 (mod 21)