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

CHAP. 11] PROPERTIES OF THE INTEGERS 285 11.10. Supposenis a positive integer. Proven≥1. (This is not true for the rational numb ...

286 PROPERTIES OF THE INTEGERS [CHAP. 11 (b) Hereais positive, butbis negative. Divideaby|b|, that is, 573 by 16, say with a cal ...

CHAP. 11] PROPERTIES OF THE INTEGERS 287 11.18. Prove Theorem 11.8 (Division Algorithm): Letaandbbe integers withb=0. Then ther ...

288 PROPERTIES OF THE INTEGERS [CHAP. 11 11.21. Leta=8316 andb=10 920. (a) Findd=gcd(a, b), the greatest common divisor ofaandb. ...

CHAP. 11] PROPERTIES OF THE INTEGERS 289 11.23. Leta= 23 · 35 · 54 · 116 · 173 andb= 25 · 53 · 72 · 114 · 132. Find gcd(a, b)and ...

290 PROPERTIES OF THE INTEGERS [CHAP. 11 Also, supposes,t∈J, say,s=x 1 a+y 1 bandt=x 2 a+y 2 b. Then, for anyn∈Z, the following ...

CHAP. 11] PROPERTIES OF THE INTEGERS 291 (a) Find the difference 446− 278 =168. Divide the difference 168 by the modulusm=7. The ...

292 PROPERTIES OF THE INTEGERS [CHAP. 11 RESIDUE SYSTEMS, EULER PHI FUNCTIONφ 11.38. For each modulom, exhibit two complete resi ...

CHAP. 11] PROPERTIES OF THE INTEGERS 293 11.44. Prove Theorem 11.25: Ifaandbare relatively prime, thenφ(ab)=φ(a)φ(b). Letaandbbe ...

294 PROPERTIES OF THE INTEGERS [CHAP. 11 11.46. InZ 11 , find: (a)−2,−5,−9,−10; (b) 2/7, 3/7, 5/7, 8/7, 10/7, 1/7. (a) Note−a=m− ...

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 ...

296 PROPERTIES OF THE INTEGERS [CHAP. 11 Divide the equation and the modulusm=2295 byd=3 to obtain the congruence equation 364 x ...

CHAP. 11] PROPERTIES OF THE INTEGERS 297 CRT tells us there is a unique solution moduloM= 21 ·10 = 210. Adding multiples of the ...

298 PROPERTIES OF THE INTEGERS [CHAP. 11 11.59. Prove Theorem 11.28: Consider the following equation whered=gcd(a, m): ax≡b(mod ...

CHAP. 11] PROPERTIES OF THE INTEGERS 299 SupplementaryProblems ORDER AND INEQUALITIES, ABSOLUTE VALUE 11.61. Insert the correct ...

300 PROPERTIES OF THE INTEGERS [CHAP. 11 DIVISIBILITY, GREATEST COMMON DIVISORS, PRIMES 11.84. Find all possible divisors of: (a ...

CHAP. 11] PROPERTIES OF THE INTEGERS 301 11.109. Find the number s of positive integers less than 3200 which are coprime to 8000 ...

302 PROPERTIES OF THE INTEGERS [CHAP. 11 11.87. (a)d = 4 = 5 ( 356 )− 37 ( 48 ); (b)d = 33 = 8 ( 165 )− 1 ( 1287 ); (c)d = 42 = ...

CHAPTER 12 Languages, Automata, Grammars 12.1Introduction This chapter discusses three topics,languages,automata, andgrammars. T ...

304 LANGUAGES, AUTOMATA, GRAMMARS [CHAP. 12 Clearly, for any wordsu,v,w, the words(uv)wandu(vw)are identical, they simply consis ...