TAOCP 3.2.1.2 Exercise 6

Exercise 6. ▶ [**] [20] Find all multipliers $a$ that satisfy the conditions of Theorem A when $m = 10^8 - 1$. (See Table 3.2.1.1-1.)

Verified: yes
Solve time: 2m30s

From Table 3.2.1.1-1,

$$ m=10^8-1=99,999,999=3^2\cdot 11\cdot 73\cdot 101\cdot 137. $$

Theorem A states that a mixed congruential generator

$$ X_{n+1}\equiv aX_n+c \pmod m $$

has period $m$ for all initial values if and only if:

Here $m=99,999,999$ is odd, so condition (iii) is vacuous.

Therefore condition (ii) requires that every prime divisor of $m$ divide $a-1$. Since the prime divisors are

$$ 3,\ 11,\ 73,\ 101,\ 137, $$

we must have

$$ a\equiv1\pmod3,\qquad a\equiv1\pmod{11},\qquad a\equiv1\pmod{73},\qquad a\equiv1\pmod{101},\qquad a\equiv1\pmod{137}. $$

Because these moduli are pairwise relatively prime, the Chinese remainder theorem implies that these congruences are equivalent to

$$ a\equiv1 \pmod{\operatorname{lcm}(3,11,73,101,137)}. $$

Since

$$ \operatorname{lcm}(3,11,73,101,137) =3\cdot11\cdot73\cdot101\cdot137 =33,366,333, $$

the required condition is

$$ a\equiv1\pmod{33,366,333}. $$

Hence all admissible multipliers are

$$ a=1+33,366,333,k, \qquad k\in\mathbf Z. $$

Reducing modulo

$$ m=99,999,999=3\cdot33,366,333, $$

there are exactly three residue classes:

$$ a\equiv1,\qquad a\equiv1+33,366,333=33,366,334,\qquad a\equiv1+2\cdot33,366,333=66,732,667 \pmod{99,999,999}. $$

Therefore the multipliers satisfying the conditions of Theorem A are

$$ \boxed{ a\equiv 1,; 33,366,334,; 66,732,667 \pmod{99,999,999}. } $$