TAOCP 3.2.2 Exercise 36
We consider the inversive congruential sequence defined by $X_{n+1} \equiv a X_n^{-1} + c \pmod{2^e}, \qquad e \ge 3, \eqno(1)$ where $a \bmod 4 = 1$ and $c \bmod 4 = 2$.
Exercise 36. [M25] Prove that the inversive congruential sequence $X_{n+1} = (aX_n^{-1} + c) \bmod 2^e$, $e \ge 3$, has period length $2^{e-1}$ whenever $a \bmod 4 = 1$ and $c \bmod 4 = 2$.
Verified: yes
Solve time: 1m31s
Solution
We consider the inversive congruential sequence defined by
$X_{n+1} \equiv a X_n^{-1} + c \pmod{2^e}, \qquad e \ge 3, \eqno(1)$
where $a \bmod 4 = 1$ and $c \bmod 4 = 2$. Our goal is to prove that this sequence has period $2^{e-1}$.
First, note that the inversive congruential generator is only defined for integers $X_n$ coprime to $2^e$, which implies that $X_n$ must be odd. Therefore the sequence takes values in the set of odd residues modulo $2^e$, which has cardinality $2^{e-1}$. Hence the maximum possible period is $2^{e-1}$.
We proceed by induction on $e$.
Base case: $e = 3$. The odd residues modulo $2^3 = 8$ are $1, 3, 5, 7$. Let $a \equiv 1 \pmod{4}$ and $c \equiv 2 \pmod{4}$. Then the sequence becomes
$X_{n+1} \equiv a X_n^{-1} + c \pmod{8}.$
Since $a \equiv 1 \pmod{4}$, we have $a \equiv 1$ or $5 \pmod{8}$, but only the congruence modulo 8 matters here. Similarly $c \equiv 2 \pmod{4}$ implies $c \equiv 2$ or $6 \pmod{8}$. Exhaustive computation shows that each odd $X_0$ produces a cycle of length $4 = 2^{3-1}$.
Inductive step: Suppose that the statement holds for $e$, i.e., the sequence modulo $2^e$ has period $2^{e-1}$ for any odd $X_0$. We show it also holds modulo $2^{e+1}$.
Let $X_n$ be the sequence modulo $2^e$, and let $\tilde{X}_n$ be the sequence modulo $2^{e+1}$ with the same initial value $X_0$ (odd). Write
$\tilde{X}_n = X_n + 2^e Y_n, \qquad Y_n \in {0,1}. \eqno(2)$
Since $X_n$ is odd, $X_n^{-1} \pmod{2^e}$ exists, and the inverse modulo $2^{e+1}$ can be expressed using Hensel's lemma as
$\tilde{X}_n^{-1} \equiv X_n^{-1} - 2^e X_n^{-2} Y_n \pmod{2^{e+1}}. \eqno(3)$
Substituting into the recurrence gives
$$ \begin{aligned} \tilde{X}_{n+1} &\equiv a \tilde{X}n^{-1} + c \pmod{2^{e+1}} \ &\equiv a (X_n^{-1} - 2^e X_n^{-2} Y_n) + c \pmod{2^{e+1}} \ &\equiv (a X_n^{-1} + c) - 2^e a X_n^{-2} Y_n \pmod{2^{e+1}} \ &\equiv X{n+1} - 2^e a X_n^{-2} Y_n \pmod{2^{e+1}}. \end{aligned} $$
Thus
$\tilde{X}{n+1} = X{n+1} + 2^e \tilde{Y}{n+1}, \quad \tilde{Y}{n+1} \equiv - a X_n^{-2} Y_n \pmod{2}. \eqno(4)$
Since $a \equiv 1 \pmod{4}$ and $X_n$ is odd, $X_n^{-2} \equiv 1 \pmod{2}$, so
$\tilde{Y}_{n+1} \equiv -Y_n \equiv Y_n + 1 \pmod{2}. \eqno(5)$
Hence the sequence $\tilde{Y}_n$ modulo 2 alternates between 0 and 1. Since the sequence $X_n$ modulo $2^e$ has period $2^{e-1}$ by the induction hypothesis, the full sequence modulo $2^{e+1}$ will have period $2 \cdot 2^{e-1} = 2^e$.
By induction, the sequence has period $2^{e-1}$ modulo $2^e$ for all $e \ge 3$.
This completes the proof.
∎
Answer: The period length of the sequence is $\boxed{2^{e-1}}$.