16 RANDOM NUMBERS 3.2.1.2 Theorem A. The linear (Make a web site)
16 RANDOM NUMBERS 3.2.1.2 Theorem A. The linear congruential sequence defined by m, a, c, and X0 has period length m if and only if i) c is relatively prime to m; ii) b = a - 1 is a multiple of p, for every prime p dividing m; iii) b is a multiple of 4, if m is a multiple of 4. The ideas used in the proof of this theorem go back at least a hundred years. The first proof of the theorem in this particular form was given by M. Greenberger in the special case m = 2e [see JACM 8 (1961), 383-3891, and the sufficiency of conditions (i), (ii), and (iii) in the general case was shown by Hull and Dobell [see SIAM Review 4 (1962), 230-2541. To prove the theorem we will first consider some auxiliary number-theoretic results that are of interest in themselves. Lemma P. Let p be a prime number, and Jet e be a positive integer, where pe > 2. If z E 1 (modulo p ), z $ 1 (modulo pe+ ), (1) then z* E 1 (modulo pefl), x* $ 1 (modulo pefa). (2) Proof. We have x = 1-t qpe for some integer q that is not a multiple of p. By the binomial formula x*=1+ I 4Pe + *** + p q*-lp(*-l)e + q*p*e 0 ( P–l > =1+qpe+l ( 1 +;(;)qp~+~~)q~p~~+…+~(;)q*-~pb-l)~). The quantity in parentheses is an integer, and, in fact, every term inside the parentheses is a multiple of p except the first term. For if 1 < k < p, the binomial coefficient (3 is divisible by p (cf. exercise 1.2.6-lo), hence is divisible by P( - )~; and the last term is q*-lp(*-l)e- , which is divisible by p since (p - 1)e > 1 when pe > 2. So zp E 1 + qpe+ (modulo pef2), and this completes the proof. (Note: A generalization of this result appears in exercise 3.2.2-11(a).) 1 Lemma Q. Let the decomposition of m into prime factors be m = pt . . . p, . (3)