3.2.1.2 CHOICE OF MULTIPLIER (Ftp web hosting) 17 The length X
3.2.1.2 CHOICE OF MULTIPLIER 17 The length X of the period of the linear congruential sequence determined by (X0, a, c, m) is the least common multiple of the lengths Xj of the periods of the linear congruential sequences (X0 mod p$ , a mod p;3f c mod pT3, p; ), 1 < j 5 t. Proof. By induction on t, it suffices to prove that if ml and m2 are relatively prime, the length X of the linear congruential sequence determined by the param- eters (X0, a, c, mlm2) is the least common multiple of the lengths X1 and X2 of the periods of the sequences determined by (X0 mod ml, a mod ml, c mod ml, ml) and (X0 mod m2, a mod m2, c mod m2, m2). We observed in the previous section, Eq. (4), that if the elements of these three sequences are respectively denoted by X,, Yn, and 2,) we will have Y, = X, mod ml and 2, =Xnmodm2, for all n > 0. Therefore, by Law D of Section 1.2.4, we find that x, =xk if and only if Y,, = Y, and 2, = 2,. (4 Let X be the least common multiple of X1 and X2; we wish to prove that A = X. Since X, = Xn+x for all suitably large n, we have Y, = Y,+x (hence X is a multiple of X1) and 2, = &+A (hence X is a multiple of X2), so we must have X 2 X . Furthermore, we know that Y, = Yn+x, and 2, = &+A, for all suitably large n; therefore, by (4), X, = X,+X,. This proves X 5 X . 1 Now we are ready to prove Theorem A. Because of Lemma Q, it suffices to prove the theorem when m is a power of a prime number. For p l . . . pi = X = lcm(X1,. . . ,X,) 5 X1 . . . Xt 5 p: . . . pz can be true if and only if X, = p; for 1 5 j 5 t. Therefore, assume that m = pe, where p is prime and e is a positive integer. The theorem is obviously true when a = 1, so we may take a > 1. The period can be of length m if and only if each possible integer 0 5 x < m occurs in the period, since no value occurs in the period more than once. Therefore the period is of length m if and only if the period of the sequence with X0 = 0 is of length m, and we are justified in supposing that X0 = 0. By formula 3.2.1-6 we have c mod m. If c is not relatively prime to m, this value X, could never be equal to 1, so condition (i) of the theorem is necessary. The period has length m if and only if the smallest positive value of n for which X, = X0 = 0 is n = m. By (5) and condition (i), our theorem now reduces to proving the following fact: