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

280 PROPERTIES OF THE INTEGERS [CHAP. 11

EXAMPLE 11.17 Consider the following congruence equation:

81 ≡ 1 (mod 256)

By observation or by applying the Euclidean algorithm to 81 and 256, we find that gcd( 81 , 256 )=1. Thus
the equation has a unique solution. Testing may not be an efficient way to find this solution since the modulus
m = 256 is relatively large. Hence, we apply the Euclidean algorithm toa=81 andm=256. Specifically,
as in Example 11.6, we findx 0 =−25 andy 0 =7 such that

81 x 0 + 256 y 0 = 1

This means thatx 0 =−25 is a solution of the given congruence equation. Addingm=256 to−25, we obtain
the following unique solution between 0 and 256:

x= 231

Linear Congruence Equation: ax≡b(modm)

Now we consider the more general linear congruence equation

ax≡b(modm) (11.4)

wherea≡0 (modm). We first consider the case (proved in Problem 11.58) whereaandmare coprime.

Theorem 11.27: Supposeaandmare relatively prime. Thenax≡b(modm) has a unique solution. Moreover,
ifsis the unique solution toax≡1 (modm), then the unique solution toax≡b(modm)is
x=bs.

EXAMPLE 11.18

(a) Consider the congruence equation 3x≡5 (mod 8). Since 3 and 8 are coprime, the equation has a unique

solution. Testing the integers 0, 1 ,...,7, we find that

3 ( 7 )= 21 ≡ 5 (mod 8)

Thusx=7 is the unique solution of the equation.

(b) Consider the linear congruence equation

33 x≡ 38 (mod 280) (11.5)

Since gcd(33, 280)=1,the equation has a unique solution. Testing may not be an efficient way to find this

solutionsince the modulusm=280 is relatively large. We apply the Euclidean algorithm to first find a

solution to

33 x≡ 1 (mod 280) (11.6)

That is, as in Example 11.6, we findx 0 =17 andy 0 =2 to be a solution of

33 x 0 + 280 y 0 = 1

This means thats=17 is a solution of (11.6). Then

sb= 17 ( 38 )= 646

is a solution of (11.5). Dividing 646 bym=280, we obtain the remainder

x= 86

which is the unique solution 11.5 between 0 and 280. (The general solution is 86+ 280 kwithk∈Z.)