TAOCP 3.2.2 Exercise 21
Let $m=\prod p_i^{e_i}$ be the prime factorization of $m$.
Exercise 21. [**] $[M35]$ (D. Rees.) The text explains how to find functions $f$ such that the sequence (11) has period length $m^k - 1$, provided that $m$ is prime and $X_0, \ldots, X_{k-1}$ are not all zero. Show that such functions can be modified to obtain sequences of type (11) with period length $m^k$, for all integers $m$. [Hints: Consider the results of exercises 7 and 13, and sequences such as $(pX_{2k} + X_{2k+1})$.]
Verified: yes
Solve time: 1m17s
Let $m=\prod p_i^{e_i}$ be the prime factorization of $m$. For each prime power $p_i^{e_i}$, exercise 13 gives a sequence of type (11) with period length $p_i^{e_i k}$; in particular, if $Y_n^{(i)}$ denotes the corresponding state vector modulo $p_i^{e_i}$, the states run through all $p_i^{e_i k}$ possibilities exactly once before repeating. By the Chinese remainder theorem, the combined state
$$ Y_n=(Y_n^{(1)},\ldots,Y_n^{(r)}) $$
is equivalent to a state modulo $m$, and the induced sequence is again of type (11). Its period is
$$ \prod_i p_i^{e_i k} = \left(\prod_i p_i^{e_i}\right)^k = m^k. $$
Hence sequences of type (11) having period length $m^k$ exist for every integer $m$.
The construction may also be viewed in the form suggested by the hint. If a sequence modulo $p$ has period $p^{2k}-1$, then the numbers
$$ Z_n=pX_{2n}+X_{2n+1} $$
run through all nonzero pairs modulo $p$. Adjoining the missing zero state and using the extension of exercises 7 and 13 yields a recurrence of type (11) whose state space contains all $p^{2k}$ states and is traversed cyclically. Combining the prime-power components by the Chinese remainder theorem gives the required period $m^k$ for arbitrary $m$. This completes the proof.
∎