RANDOM NUMBERS 3.2.1.2 Lemma R. Assume that 1 (Web hosting companies)
RANDOM NUMBERS 3.2.1.2 Lemma R. Assume that 1 < a < pe, where p is prime. If X is the smallest positive integer for which (aX - l)/(a -1) s 0 (modulo p ), then a s 1 (modulo p) when p > 2, x = pe if and only if a z 1 (modulo 4) when p= 2. Proof. Assume that X = pe. If a $ 1 (modulo p), then (an -l)/(a -1) G 0 (modulo p ) if and only if an -1 E 0 (modulo p ). The condition ape - 1 E 0 (modulo p ) then implies that ape E 1 (modulo p); but by Theorem 1.2.4F we have ape s a (modulo p), hence a $ 1 (modulo p) leads to a contradiction. And if p = 2 and a zz 3 (modulo 4), we have (aze- -l)/(a -1) E 0 (modulo 2e) by exercise 8. These arguments show that it is necessary in general to have a = 1 + qpf , where pf > 2 and q is not a multiple of p, whenever X = pe. It remains to be shown that this condition is sufficient to make X = pe. By repeated application of Lemma P, we find that apg E 1 (modulo P~+~), apg f 1 (modulo P~+~+ ), for all g 2 0, and therefore (up9 -l)/(a -1) E 0 (modulo pg) , (apg -l)/(a -1) $ 0 (modulo pgfl). (6) In particular, (a pe - l)/(a-1) 3 0 (modulo p ). Now the congruential sequence (0, a, 1, p ) has X, = (a -l)/(a-1) modp ; therefore it has a period of length X, that is, X, = 0 if and only if n is a multiple of X. Hence pe is a multiple of X. This can happen only if X = pg for some g, and the relations in (6) imply that X = pe, completing the proof. I The proof of Theorem A is now complete. 4 We will conclude this section by considering the special case of pure mul- tiplicative generators, when c = 0. Although the random number generation process is slightly faster in this case, Theorem A shows us that the maximum period length cannot be achieved. In fact, this is quite obvious, since the sequence now satisfies the relation X n+l = ax, mod m, (7) and the value X, = 0 should never appear, lest the sequence degenerate to zero. In general, if d is any divisor of m and if X, is a multiple of d, all succeeding elements X,+1, Xn+2, . . . of the multiplicative sequence will be multiples of d. So when c = 0, we will want X, to be relatively prime to m for all n, and this limits the length of the period to at most p(m), the number of integers between 0 and m that are relatively prime to m.