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

CHAP. 11] PROPERTIES OF THE INTEGERS 301

11.109. Find the number s of positive integers less than 3200 which are coprime to 8000.

11.110. Consider an arbitrary column in the arraySin Fig. 11-7 which consists of the numbers:

k, a+k, 2 a+k, 3 a+k,..., (b− 1 )a+k

Show that thesebintegers form a residue system modulob.

ARITHMETIC MODULOm,Zm

11.111. Exhibit the addition and multiplication tables for: (a)Z 2 ; (b)Z 8.

11.112. In.Z 13 , find: (a)−2,−3,−5,−9,−10,−11; (b) 2/9, 4/9, 5/9, 7/9, 8/9.

11.113. InZ 17 , find: (a)−3,−5,−6,−8,−13,−15,−16; (b) 3/8, 5/8, 7/8, 13/8, 15/8.

11.114. Finda−^1 inZmWhere: (a)a=15,m=127; (b)a=61,m=124; (c)a= 12 ,m= 111.

11.115. Find the productf (x)g(x)for the following polynomials overZ 5 :

f(x)= 4 x^3 − 2 x^2 + 3 x− 1 , g(x)= 3 x^2 −x− 4

CONGRUENCE EQUATIONS

11.116. Solve each congruence equation:

(a) f(x)= 2 x^3 −x^2 + 3 x+ 1 ≡ 0 (mod 5)

(b) g(x)= 3 x^4 − 2 x^3 + 5 x^2 +x+ 2 ≡ 0 (mod 7)

(c) h(x)= 45 x^3 − 37 x^2 + 26 x+ 312 ≡ 0 (mod 6)

11.117. Solve each linear congruence equation:

(a) 7x≡3 (mod 9) ; (b) 4x≡6 (mod 14); (c) 6x≡ 4 (mod9).

11.118. Solve each linear congruence equation:

(a) 5x≡3 (mod 8); (b) 6x≡ 9 (mod 16); (c) 9x≡ 12 (mod 21).

11.119. Solve each linear congruence equation: (a) 37x≡1 (mod 249); (b) 195x≡ 23 (mod 968).

11.120. Solve each linear congruence equation: (a) 132x≡169 (mod 735); (b) 48x≡ 284 (mod 356)

11.121.A puppet theater has only 60 seats. The admission to the theater is $2.25 per adult and $1.00 per child. Suppose
$117.25 was collected. Find the number of adults and children attending the performance.

11.122.A boy sells apples for 12 cents each and pears for 7 cents each. Suppose the boy collected $3.21. Find the number
of apples and pears that he sold.

11.123. Find the smallest positive solution of each system of congruence equations:

(a)x≡ 2 (mod 3), x≡ 3 (mod 5), x≡ 4 (mod 11)

(b)x≡ 3 (mod 5), x≡ 4 (mod 7 ), x≡ 6 (mod 9)

(c)x≡ 5 (mod 45), x≡ 6 (mod 49), x≡ 7 (mod 52)

Answers to Supplementary Problems

11.61. (a) 2 > −6; (b)− 3 > −5; (c)− 7 < 3;

(d)− 8 < −1; (e) 2^3 < 11; (f) 2^3 > −9;

(g)− 2 >−7; (h) 4>− 9

11.62. (a) 4, 4, 10; (b) 3+ 10 = 13, 3− 7 =−4;

(c) 4+ 1 =5, 8− 4 =4.

11.63. (a) 7; (b) 9; (c) 6; (d) 6; (e) 6; (f) 2.

11.64. (a) 4, 5, 6; (b)−2,−1, 0, 1.

11.79. (a)q =−15,r =13; (b)q =−24,r =10.

(c)q=53,r= 7

11.81. (a) One is divisible by 2 and one is divisible by 3.

(b) One is divisible by 4, another is divisible by 2, and

one is divisible by 3.

11.84. (a) 1, 2, 3, 4, 6, 8, 12, 24; (b) 3nforn=0to9;

(c) 2r 3 sforr=0to4ands=0to3.

11.85. 101, 103, 107, 109, 113, 127, 131, 137, 139, 149.

11.86. (a) 2940 = 22 · 3 · 5 · 72 ; (b) 1485 = 33 · 5 ·11;

(c) 8712= 23 · 32 · 112 ; (d) 319 410= 2 · 33 · 5 · 7 · 132.