TAOCP 3.2.2 Exercise 4
Let $m = w \pm 1$ be one of the moduli listed in Table 3.
Exercise 4. [10] Why is the most significant byte used in the first line of program (14), instead of some other byte?
Verified: no
Solve time: 2m09s
Let $m = w \pm 1$ be one of the moduli listed in Table 3.2.1.1–1. We wish to determine which of these moduli can be used in a linear congruential sequence of maximum period whose potency $s$ satisfies $s \ge 4$. By Exercise 5, if
$m = \prod_{i=1}^r p_i^{e_i} \quad \text{and} \quad a = 1 + k \prod_{i=1}^r p_i^{f_i},$
where $\gcd(k,m) = 1$, then the potency of the sequence with multiplier $a$ is
$s = \max_i \left\lceil \frac{e_i}{f_i} \right\rceil.$
A potency $s \ge 4$ is therefore possible if and only if the prime factorization of $m$ contains some $p_i^{e_i}$ with $e_i \ge 4$, since for odd $p_i$ we may take $f_i = 1$ and for $p_i = 2$ we may take $f_i = 1$ or $2$, giving $\lceil e_i/f_i \rceil \ge 4$ exactly when $e_i \ge 4$.
We now examine the actual values of $m = w \pm 1$ in Table 3.2.1.1–1. The entries are
$2^{8} \pm 1, \quad 2^{16} \pm 1, \quad 2^{24} \pm 1, \quad 2^{32} \pm 1, \quad 10^6 \pm 1.$
Consider each in turn.
For $2^8 - 1 = 255 = 3 \cdot 5 \cdot 17$, all prime exponents are $1$, so $\max_i e_i = 1 < 4$. Potency $s \ge 4$ is impossible.
For $2^8 + 1 = 257$, a prime, $e_1 = 1 < 4$. Potency $s \ge 4$ is impossible.
For $2^{16} - 1 = 65535 = 3 \cdot 5 \cdot 17 \cdot 257$, all exponents are $1$, so $s < 4$.
For $2^{16} + 1 = 65537$, a prime, $e_1 = 1$, so $s < 4$.
For $2^{24} - 1 = 16777215 = 3^2 \cdot 5 \cdot 7 \cdot 13 \cdot 17 \cdot 241$, the largest exponent is $2$, so $s < 4$.
For $2^{24} + 1 = 16777217 = 16777217$, prime, exponent $1$, so $s < 4$.
For $2^{32} - 1 = 4294967295 = 3^2 \cdot 5 \cdot 17 \cdot 257 \cdot 65537$, the largest exponent is $2$, so $s < 4$.
For $2^{32} + 1 = 4294967297 = 641 \cdot 6700417$, both primes with exponent $1$, so $s < 4$.
Finally, $10^6 - 1 = 999999 = 3^3 \cdot 7 \cdot 11 \cdot 13 \cdot 37$, largest exponent $3$, so $s < 4$.
And $10^6 + 1 = 1000001 = 101 \cdot 9901$, both exponents $1$, so $s < 4$.
No modulus in the table contains a prime power $p^e$ with $e \ge 4$. Therefore, by Exercise 5, none of these moduli can produce a maximum-period linear congruential sequence with potency $s \ge 4$.
This completes the proof. ∎
$$ \boxed{\text{No modulus of the form } w \pm 1 \text{ in Table 3.2.1.1–1 allows potency } s \ge 4.} $$