Make web site - 3.2.1.2 CHOICE OF MULTIPLIER 21 4. [M20] When
3.2.1.2 CHOICE OF MULTIPLIER 21 4. [M20] When a and c satisfy the conditions of Theorem A, and when m = 2e, Xe = 0, what is the value of X2,-1? 5. [14] Find all multipliers a that satisfy the conditions of Theorem A when m = 235 + 1. (The prime factors of m may be found in Table 3.2.1.1-1.) b 6. [Z O] Find all multipliers a that satisfy the conditions of Theorem A when m = lo6 -1. (See Table 3.2.1.1-l.) l 7. [M23] The period of a congruential sequence need not start with X0, but we can always find indices p 2 0 and X > 0 such that Xn+x = X, whenever n 2 p, and for which ,U and X are the smallest possible values with this property. (Cf. exercises 3.1-6 and 3.2.1-1.) If p~j and Xj are the indices corresponding to the sequences (X0 modpJ3, a mod pT3, c modpJT3, p;j), and if ,LL and X correspond to the sequence (X0, a, c, p; . . . pet), Lemma Q states that X is the least common multiple of X1, . . . , Xt. What is the value of p in terms of the values of ~1, . . . , pt? What is the maximum possible value of /J obtainable by varying X0, a, and c, when m = p; . . . pz is fixed? 8. [M20] Show that if amod = 3, we have (a - -l)/(a -1) 3 0 (modulo 2 ) when e > 1. (Use Lemma P.) b 9. [MZ2] (W. E. Thomson.) When c = 0 and m = 2 > 16, Theorems B and C say that the period has length 2e-2 if and only if the multiplier a satisfies amod = 3 or amod 8 = 5. Show that every such sequence is essentially a linear congruential sequence with m = 2e–2, having full period, in the following sense: a) If Xn+l = (4c $1)X% mod 2e, and X, = 4Y, + 1, then Y n+l = ((4~ + l)Y, $ ~)mod2 -~. b) If Xn+r = (4c - l)Xn mod2 , and X, = ((-l)n(4Y, + l))mod2 , then Yn+~ = ((1 -4c)Y, -c) mod Ze- . [Note: In these formulas, c is an odd integer. The literature contains several statements to the effect that sequences with c = 0 satisfying Theorem B are somehow more random than sequences satisfying Theorem A, in spite of the fact that the period is only one-fourth as long in the case of Theorem B. This exercise refutes such statements; in essence, one gives up two bits of the word length in order to save the addition of c, when m is a power of 2.1 10. (MB] For what values of m is k(m) = cp(m)? b 11. [ML%] Let x be an odd integer greater than 1. (a) Show that there exists a unique integer f > 1 such that x 3 af f 1 (modulo 21t1). (b) Given that 1 < x < 2e - 1 and that f is the corresponding integer from part (a), show that the order of x modulo 2 is 2e-f. (c) In particular, this proves Theorem C(i). 12. [M26] Let p be an odd prime. If e > 1, prove that a is a primitive element modulo pe if and only if a is a primitive element modulo p and ape1 $ 1 (modulo p ). (For the purposes of this exercise, assume that X(p ) = p - (p-1). This fact is proved in exercises 14 and 16 below.) 13. [M22] Let p be prime. Given that a is not a primitive element modulo p, show that either a is a multiple of p or CJ@- )/~ G 1 ( modulo p) for some prime number o that divides p - 1.