TAOCP 3.2.1.2 Exercise 5
We are asked to find all multipliers $a$ that satisfy the conditions of Theorem A when $m = 2^{35} + 1$.
Section 3.2.1.2: Choice of Multiplier
Exercise 5. [14] Find all multipliers $a$ that satisfy the conditions of Theorem A when $m = 2^{35} + 1$. (The prime factors of $m$ may be found in Table 3.2.1.1–1.)
Verified: yes
Solve time: 1m31s
Solution
We are asked to find all multipliers $a$ that satisfy the conditions of Theorem A when $m = 2^{35} + 1$. Let us proceed systematically.
First, factor $m$. From Table 3.2.1.1–1 we know that
$$ m = 2^{35} + 1 = 3 \cdot 23 \cdot 89 \cdot 683 \cdot 2113. $$
Let us denote the prime factorization as
$$ m = p_1 p_2 p_3 p_4 p_5, $$
with $p_1 = 3$, $p_2 = 23$, $p_3 = 89$, $p_4 = 683$, $p_5 = 2113$.
Theorem A states that the linear congruential sequence with modulus $m$ has maximum period $m$ if and only if the following three conditions hold:
i) $c$ is relatively prime to $m$;
ii) $b = a - 1$ is a multiple of $p$, for every prime $p$ dividing $m$;
iii) $b$ is a multiple of $4$ if $m$ is a multiple of $4$.
Since $m$ is odd, condition (iii) is automatically satisfied. Condition (i) is independent of $a$, so we focus on condition (ii).
Condition (ii) requires
$$ a - 1 \equiv 0 \pmod{p_j} \quad \text{for each } j = 1,\dots,5. $$
Equivalently,
$$ a \equiv 1 \pmod{p_j} \quad \text{for each } j = 1,\dots,5. $$
Because the $p_j$ are distinct primes, we may apply the Chinese remainder theorem. Let
$$ P = p_1 p_2 p_3 p_4 p_5 = 3 \cdot 23 \cdot 89 \cdot 683 \cdot 2113 = m. $$
Since the primes are pairwise coprime, there is exactly one congruence class modulo $m$ that simultaneously satisfies
$$ a \equiv 1 \pmod{3}, \quad a \equiv 1 \pmod{23}, \quad a \equiv 1 \pmod{89}, \quad a \equiv 1 \pmod{683}, \quad a \equiv 1 \pmod{2113}. $$
This class is
$$ a \equiv 1 \pmod{m}. $$
Hence the only integer $a$ in the range $1 \le a < m$ that satisfies condition (ii) is
$$ \boxed{a = 1}. $$
This completely characterizes all multipliers satisfying Theorem A for $m = 2^{35} + 1$. No other integers satisfy condition (ii), and condition (iii) is irrelevant because $m$ is odd. Condition (i) concerns $c$ and does not further restrict $a$.
This completes the solution. ∎