22 RANDOM NUMBERS 3.2.1.2 14. [Ml81 If e
22 RANDOM NUMBERS 3.2.1.2 14. [Ml81 If e > 1 and p is an odd prime, and if a is a primitive element modulo p, prove that either a or a + p is a primitive element modulo pe. [Hint: See exercise 12.1 15. [A4991 (a) Let al, a2 be relatively prime to m, and let their orders modulo m be X1, X2, respectively. If X is the least common multiple of Xi and X2, prove that a;E1atZ has order X modulo m, for suitable integers ICY, ~2. [Hint: Consider first the case that X1 is relatively prime to X2.1 (b) Let x(m) be the maximum order of any element modulo m. Prove that x(m) is a multiple of the order of each element modulo m; that is, prove that a Vrn) =_ 1 (modulo m) whenever a is relatively prime to m. b 16. [M2?4] Let p be a prime number. (a) Let f(x) = xn + clxn-- +. . . + cn, where the c s are integers. Given that a is an integer for which f(a) = 0 (modulo p), show that there exists a polynomial q(x) = xn- + qixn- + … $- qn-i with integer coefficients such that f(z) = (x - a)q(s) (modulo p) for all integers Z. (b) Let f(x) be a polynomial as in (a). Show that f(x) h as at most n distinct roots modulo p; that is, there are at most n integers a, with 0 5 a < p, such that f(a) = 0 (modulo p). (c) Because of exercise 15(b), the polynomial f(x) = ~ (~1 -1 has p -1 distinct roots; hence there is an integer a with order p - 1. 17. [A!.%] Not all of the values listed in Theorem D would be found by the text s construction; for example, 11 is not primitive modulo 5e. How can this be possible, when 11 is primitive modulo lo , according to Theorem D? Which of the values listed in Theorem D are primitive elements modulo both 2 and 5 ? 18. [A4851 Prove Theorem D. (Cf. the previous exercise.) 19. [40] Make a table of some suitable multipliers, a, for each of the values of m listed in Table 3.2.1.1-1, assuming that c = 0. b 20. [M24] (G. Marsaglia.) The purpose of this exercise is to study the period length of an arbitrary linear congruential sequence. Let Y,, = 1 + a + . . . + an- , so that X, = (AY, + Xc)modm for some constant A by Eq. 3.2.1-8. (a) Prove that the period length of (Xn) is the period length of (Yn mod m ), where m = m/gcd(A, m). (b) Prove that the period length of (Y, modp ) satisfies the following when p is prime: (i)Ifumodp=O,itisl. (ii)Ifumodp=1,itispe,exceptwhenp=2ande>2and a mod 4 = 3. (iii) If p = 2, e 2 2, and a mod 4 = 3, it is twice the order of a modulo pe (cf. exercise ll), unless a F -1 (modulo 2e) when it is 2. (iv) If umodp > 1, it is the order of a modulo pe. 21. [M.Z5] In a linear congruential sequence of maximum period, let Xc = 0 and let s be the least positive integer such that us = 1 (modulo m). Prove that gcd(X,, m) = s. 3.2.1.3. Potency. In the preceding section, we showed that the maximum period can be obtained when b = a -1 is a multiple of each prime dividing m; and b must also be a multiple of 4 if m is a multiple of 4. If z is the radix of the machine being used-so that z = 2 for a binary computer, and z = 10 for a decimal computer-and if m is the word size ze, the multiplier. a=zk+l, 2