522 ANSWERS TO EXERCISES 3.2.1.1 7. The prime
522 ANSWERS TO EXERCISES 3.2.1.1 7. The prime factors of zk -1 appear in the factorization of zkr -1. If T is odd, the prime factors of zk f 1 appear in the factorization of zkr + 1. And zzk -1 equals (z -l)(zk + 1). 8. JOV *+1 (Ensure that overflow is off.) LDA X MULA STX TEMP ADD TEMP Add lower half to upper half. JNOV *+2 If 2 w, subtract w -1. INCA 1 (Overflow is impossible in this step.) 1 Note: Since addition on an e-bit ones -complement computer is mod (2e -l), it is possible to combine the techniques of exercises 4 and 8, producing (yz)mod(2 -1) by adding together the two e-bit halves of the product yz, for all ones complement numbers y and z regardless of sign. 9. The pairs (0, w -2), (1, w -1) are treated as equivalent in input and output: JOV *+I LDA X MULA aX=qw+r. SLC 5 rA + r, rX + q. STX TEMP ADD TEMP JNOV *+2 Get (r + q) mod (w -2). INCA 2 Overflow is impossible. ADD TEMP JNOV *+3 Get (r + 2q) mod (w -2). INCA 2 Overflow is possible. JOV *-I 1 SECTION 3.2.1.2 1. Period length m, by Theorem A. (Cf. exercise 3.) 2. Yes, these conditions imply the conditions in Theorem A, since the only prime divisor of 2e is 2, and any odd number is relatively prime to 2 . (In fact, the conditions of the exercise are necessary and sufficient.) 3. By Theorem A, we need a E 1 (modulo 4) and a = 1 (modulo 5). By Law D of Section 1.2.4, this is equivalent to a z 1 (modulo 20). 4. We know Xze-l E 0 (modulo 2e-1) by using Theorem A in the case m = 2+ . Also using Theorem A for m = 2 , we know that Xze-l $ 0 (modulo 27. It follows that X,.-l = 2e-1. More generally, we can use Eq. 3.2.1-6 to prove that the second half of the period is essentially like the first half, since XnfZe–l = (Xn+2e-1) mod 2e. (The quarters are similar too, see exercise 21.) 5. We need a = 1 (modulo p) for p = 3,11,43,281,86171. By Law D of Section 1.2.4, this is equivalent to a 3 1 (modulo 3. 11 . 43. 281 . 86171), so the only solution is the terrible multiplier a = 1.