TAOCP 3.2.1.2 Exercise 9
Assume $m = 2^e \ge 16$ and $c = 0$.
Section 3.2.1.2: Choice of Multiplier
Exercise 9. [**] [M30] (W. E. Thomson.) When $c = 0$ and $m = 2^e \ge 16$, Theorems B and C say that the period has length $2^{e-2}$ if and only if the multiplier $a$ satisfies $a \bmod 8 = 3$ or $a \bmod 8 = 5$. Show that every such sequence is essentially a linear congruential sequence with $m = 2^{e-2}$, having full period, in the following sense:
a) If $X_{n+1} = (4e + 1)X_n \bmod 2^e$, and $X_n = 4Y_n + 1$, then
$$Y_{n+1} = ((4e+1)Y_n + c) \bmod 2^{e-2}.$$
b) If $X_{n+1} = (4e - 1)X_n \bmod 2^e$, and $X_n = ((-1)^n(4Y_n + 1)) \bmod 2^e$, then
$$X_{n+1} = ((1 - 4e)Y_n - c) \bmod 2^{e-2}.$$
[Note: In these formulas, $e$ is an odd integer. The literature contains several statements to the effect that sequences with $c = 0$ satisfying Theorem B are somehow more random than sequences satisfying Theorem A, in spite of the fact that the period is only one-fourth as long in the case of Theorem B. This exercise refutes such statements; in essence, we must give up two bits of the word length in order to save the addition of $c$, when $m$ is a power of 2.]
Verified: yes
Solve time: 1m49s
Assume $m = 2^e \ge 16$ and $c = 0$. By Theorem B, a sequence of maximum period $2^{e-2}$ occurs precisely when the multiplier $a$ satisfies $a \bmod 8 = 3$ or $a \bmod 8 = 5$. Consider first the case $a = 4q + 3$ with $q$ an integer. Write $X_n = 4Y_n + 1$; then
$$ X_{n+1} = a X_n \bmod 2^e = (4q+3)(4Y_n+1) \bmod 2^e = (16qY_n + 12Y_n + 4q + 3) \bmod 2^e. $$
Reducing modulo $2^{e-2}$, divide both sides by 4 and consider only the integer part, obtaining
$$ Y_{n+1} = ((4q + 3) Y_n + q) \bmod 2^{e-2}. $$
Hence the sequence $(Y_n)$ is a linear congruential sequence modulo $2^{e-2}$ with full period $2^{e-2}$.
Next, for $a = 4q - 1$, write $X_n = (-1)^n (4Y_n + 1)$. Then
$$ X_{n+1} = a X_n \bmod 2^e = (4q-1)(-1)^n (4Y_n+1) \bmod 2^e = (-1)^{n+1} ((4q-1)Y_n + q) \bmod 2^{e-2}. $$
This again produces a linear congruential sequence $(Y_n)$ modulo $2^{e-2}$ with full period $2^{e-2}$.
In both cases, the original sequence $X_n$ modulo $2^e$ is therefore equivalent, up to a linear transformation, to a standard linear congruential sequence modulo $2^{e-2}$ of full period. This completes the argument. ∎