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

CHAP. 11] PROPERTIES OF THE INTEGERS 295

Fig. 11-11

CONGRUENCE EQUATIONS

11.51. Solve the congruence equationf(x)= 4 x^4 − 3 x^3 + 2 x^2 + 5 x− 4 ≡0 (mod 6).

Since the equation is not linear, we solve the equation by testing the numbers in a complete residue system

modulo 6, say, {0, 1, 2, 3, 4, 5}. We have:

f( 0 )= 4 ≡ 0 (mod 6), f ( 2 )= 54 ≡ 0 (mod 6), f ( 4 )= 880 ≡ 4 ≡ 0 (mod 6)

f( 1 )= 4 ≡ 0 (mod 6), f ( 3 )= 272 ≡ 2 ≡ 0 (mod 6), f ( 5 )= 2196 ≡ 0 (mod 6)

Thus only 2 and 5 are roots off(x)modulo 6. That is, {2, 5} is a complete set of solutions.

11.52. Solve the congruence equationf(x)= 26 x^4 − 31 x^3 + 46 x^2 − 76 x+ 57 ≡0 (mod 8).

First we reduce the coefficients off(x)modulo 8 to obtain the equivalent congruence equation

g(x)= 2 x^4 − 7 x^3 + 6 x^2 − 4 x+ 1 ≡ 0 (mod 8)

Since 7≡−1 (mod 8) and 6 =−2 (mod 8), we can further simplify our original equation to obtain the equivalent

congruence equation

h(x)= 2 x^4 +x^3 − 2 x^2 − 4 x+ 1 ≡ 0 (mod 8)

We test the numbers in a complete residue system modulo 8 and, in order to keep our arithmetic as simple as

possible, we choose{− 3 ,− 2 ,− 1 , 0 , 1 , 2 , 3 , 4 }. (That is, we chose those numbers whose absolute value is minimal.)

Substituting these numbers inh(x)we obtain:

h(− 3 )= 130 ≡ 2 (mod 8), h( 0 )= 1 ≡ 1 (mod 8), h( 3 )= 160 ≡ 0 (mod 8)

h(− 2 )= 9 ≡ 1 (mod 8), h( 1 )=− 2 ≡ 6 (mod 8), h( 4 )= 529 ≡ 1 (mod 8)

h(− 1 )= 4 ≡ 4 (mod 8 ), h( 2 )= 25 ≡ 1 (mod 8 ),

Thus 3 is the only solution off(x)(mod 8).

11.53. Solve each linear congruence equation:

(a)3x≡2 (mod 8); (b)6x≡5 (mod 9); (c)4x≡6 (mod 10)

Since the moduli are relatively small, we find all the solutions by testing. Recallax≡b(modm) has exactly

d=gcd(a, m)solution providingddividesb.

(a) Here gcd( 3 , 8 )=1, hence the equation has a unique solution. Testing 0, 1 , 2 ,...,7, we find that 3( 6 )= 18 ≡ 2

(mod 8). Thus 6 is the unique solution.

(b) Here gcd( 6 , 9 )=3, but 3 does not divide 5. Hence the system has no solution.

(c) Here gcd( 4 , 10 )=2 and 2 divides 6; hence the system has two solutions. Testing 0, 1 , 2 , 3 ,...,9, we see that

4 ( 4 )= 16 ≡ 6 (mod 10) and 4( 9 )= 36 ≡ 6 (mod 10 )

Hence4 and 9 are our two solutions.

11.54. Solve the congruence equation 1092x≡213 (mod 2295).

Testing is not an efficient way to solve this equation since the modulusm=2295 is large. First use the

Euclidean algorithm to findd=gcd( 1092 , 2295 )=3. Dividing 213 byd=3 yields 0 as a remainder; that is, 3

does divide 213. Thus the equation will have three (incongruent) solutions.