524 ANSWERS (Web site construction) TO EXERCISES 3.2.1.2 16. (a) f(z)
524 ANSWERS TO EXERCISES 3.2.1.2 16. (a) f(z) = (z -a)(~?-~ + (a + ci)~?-~ +. . . + (an- -j-. . . + ~-1)) + f(a). (b) The statement is clear when n = 0. If a is one root, f(s) = (z -a)q(z); therefore if a is any other root, 0 G f(d) E (a -u)q(a ), and since a -a is not a multiple of p, a must be a root of q(z). So if f(s) has more than n distinct roots, q(z) has more than n -1 distinct roots. (c) X(p) 2 p -1, since f(z) must have degree 2 p -1 in order to possess so many roots. But by Theorem 1.2.4F, X(p) 2 p-1. 17. By Lemma P, 115 f 1 (modulo 25) 115 $ 1 (modulo 125), etc.; so the order of 11 is 5+-l (modulo 5e), not the maximum value X(5e) = 4. gem . But by Lemma Q the total period length is the least common multiple of the period modulo 2 (namely 2 - ) and the period modulo 5 (namely 5e-1), and this is 2e-25e-1 = X(lOe). The period modulo 5e may be ge- or 2 . ge- or 4 . 5=-l, without affecting the length of period modulo 10e, since the least common multiple is taken. The values that are primitive modulo 5 are those congruent to 2, 3, 8, 12, 13, 17, 22, 23 modulo 25 (cf. exercise 12), namely 3, 13, 27, 37, 53, 67, 77, 83, 117, 123, 133, 147, 163, 173, 187, 197. 18. According to Theorem C, umod 8 must be 3 or 5. Knowing the period of a modulo 5 and modulo 25 allows us to apply Lemma P to determine admissible values of a mod 25. Period = 4. ge- : 2, 3, 8, 12, 13, 17, 22, 23; period = 2. 5e-1: 4, 9, 14, 19; period = 5e-1: 6, 11, 16, 21. Each of these 16 values yields one value of a, 0 5 a < 200, with a mod 8 = 3, and another value of a with a mod 8 = 5. 19. One example appears in Table 3.3.4-1, line 26. 20. (a) We have AY, +X0 G AY,+k + X0 (modulo m) iff Y, = Yn+k (modulo m ). (b)(i) Obvious. (ii) Theorem A. (iii) (a -l)/(u -1) = 0 (modulo 2e) iff un z 1 (modulo 2ef1); if a $ -1, the order of a modulo 2 + is twice its order modulo 2 . (iv) (a -l)/(u -1) z 0 (modulo p ) iff un E 1. 21. X,+, = X, + X, by Eq. 3.2.1-6; and s is a divisor of m, since s is a power of p when m is a power of p. Hence a given integer q is a multiple of m/s iff X,, = 0 iff q is a multiple of m/ gcd(X,, m). SECTION 3.2.1.3 1. c = 1 is always relatively prime to B5; and every prime dividing m = B5 is a divisor of B, so it divides b = B2 to at least the second power. 2. Only 3, so the generator is not recommended in spite of its long period. 3. The potency is 18 in both cases (see next exercise). 4. Since umod4 = 1, we must have umod8 = 1 or 5, so bmod8 = 0 or 4. If b is an odd multiple of 4, and if bl is a multiple of 8, clearly bS = 0. (modulo 2 ) implies that bi = 0 (modulo 2 ), so bl cannot have higher potency. 5. The potency is the smallest value of s such that fjS 2 e3 for all j. 6. The modulus must be divisible by 27 or by p4 (for odd prime p) in order to have a potency as high as 4. The only values are m = 227 + 1 and 10 -1. 7. a = (1 -b + b2 -. .) mod m, where the terms in b , bsfl, etc., are dropped (if s is the potency).