TAOCP 3.2.2 Exercise 22
Let m=p_1p_2\cdots p_t, where the primes $p_1,\ldots,p_t$ are distinct.
Exercise 22. ▶ [**] $[M24]$ The text restricts discussion of the extended linear sequences (8) to the case that $m$ is prime. Prove that reasonably long periods can also be obtained when $m$ is "squarefree," that is, the product of distinct primes. (Examination of Table 3.2.1.1 shows that $m = w \pm 1$ often satisfies this hypothesis; many of the results of the text can therefore be carried over to that case, which is somewhat more convenient for calculation.)
Verified: no
Solve time: 2m06s
Let
$$ m=p_1p_2\cdots p_t, $$
where the primes $p_1,\ldots,p_t$ are distinct. By the Chinese remainder theorem, the residue class ring modulo $m$ is isomorphic to the direct product of the fields modulo $p_i$. Hence the recurrence
$$ X_n=(a_1X_{n-1}+\cdots+a_kX_{n-k})\bmod m $$
induces independent recurrences modulo each $p_i$.
Choose coefficients $a_1,\ldots,a_k$ so that the characteristic polynomial (9) is primitive modulo every $p_i$. Then, for each prime factor $p_i$, the corresponding sequence modulo $p_i$ has period
$$ p_i^k-1, $$
provided that the initial values are not all $0$ modulo $p_i$, by the theory developed in the text. The sequence modulo $m$ repeats exactly when all of its projections modulo the $p_i$ repeat simultaneously; therefore its period is
$$ \operatorname{lcm}(p_1^k-1,\ldots,p_t^k-1). $$
This period is large. In particular,
$$ \operatorname{lcm}(p_1^k-1,\ldots,p_t^k-1) \ge \frac{(p_1^k-1)\cdots(p_t^k-1)} {\prod_{i<j}(p_i^k-1,p_j^k-1)}, $$
and each factor $p_i^k-1$ is of order $p_i^k$. Thus the period is of the same general magnitude as $m^k$, differing only by factors arising from common divisors of the numbers $p_i^k-1$. Consequently, extended linear sequences (8) with squarefree modulus $m$ can have periods that are reasonably close to the maximal periods obtained in the prime-modulus case.
This completes the proof.
∎