Mathematics for Computer Science

8.13. References 293 Problem 8.28. The values of polynomialp.n/WWDn^2 CnC 41 are prime for all the integers from 0 to 39 (see Se ...

Chapter 8 Number Theory294 Problems for Section 8.7 Practice Problems Problem 8.29. A majority of the following statements are e ...

8.13. References 295 (a)For exactly what integersk > 1is it true that the sum of the digits of the base 16 representation of ...

Chapter 8 Number Theory296 Problem 8.33. This problem will use elementary properties of congruences to prove that every positive ...

8.13. References 297 Class Problems Problem 8.34. Find remainder  98763456789 999
5555 67893414259 ; 14  : (8.39) Problem ...

Chapter 8 Number Theory298 (a)Explain why (8.40) does not follow immediately from Euler’s Theorem. (b)Prove that d^13 d .mod10/ ...

8.13. References 299 Problem 8.40. We define the sequence of numbers anD ( 1; forn 3 , an 1 Can 2 Can 3 Can 4 ; forn > 3. Us ...

Chapter 8 Number Theory300 (b)Assumen > 1. Explain how to use the numbersx;yto find the inverse ofm modulonwhen there is an i ...

8.13. References 301 Problems for Section 8.10 Practice Problems Problem 8.47. Prove thatk 2 Œ0;n/has an inverse moduloniff it h ...

Chapter 8 Number Theory302 Problem 8.52. (a)What is the probability that an integer from 1 to 360 selected with uniform probabil ...

8.13. References 303 Problem 8.58. Supposea;bare relatively prime and greater than 1. In this problem you will prove theChinese ...

Chapter 8 Number Theory304 Now supposep > 2is a prime of the form 2 sC 1. For example, 21 C1;2^2 C 1;2^4 C 1 are such primes. ...

8.13. References 305 Problem 8.62. Supposea;bare relatively prime integers greater than 1. In this problem you will prove that E ...

Chapter 8 Number Theory306 Problem 8.64. The general version of the Chinese Remainder Theorem(see Problem 8.58) extends to more ...

8.13. References 307 (a)Show that ifpidoes not dividea, then a.m/1 .modpkii/: (b)Show that ifpijathen am.m/0 .modpiki/: (8.4 ...

Chapter 8 Number Theory308 (e)If gcd.a;b/¤ 1 and gcd.b;c/¤ 1 , then gcd.a;c/¤ 1. true false (f)If an integer linear combination ...

8.13. References 309 (c)Call a number from 0 to 174powerfuliff some positive power of the number is congruent to 1 modulo 175. W ...

Chapter 8 Number Theory310 Problem 8.73. (a)Show that ifpjnfor some primepand integern > 0, then .p1/j.n/. (b)Conclude that ...

8.13. References 311 his private key as though it was someone’s public key. That is, from a plain text m 2 Œ0;n/, Pete would bro ...

Chapter 8 Number Theory312 TryeD3;5;7;:::until you find something that works. Use Euclid’s algo- rithm to compute the gcd. Fin ...