TAOCP 3.2.2 Exercise 14
Let $(X_n)$ and $(Y_n)$ be integer sequences modulo $m$ with periods $\lambda_1$ and $\lambda_2$, respectively.
Exercise 14. [M24] Let $X_n$, $Y_n$, $Z_n$, $\lambda_1$, $\lambda_2$, $\lambda_3$ be as in the previous exercise. Suppose that the prime factorization of $\lambda_1$ is $2^{e_2} 3^{e_3} 5^{e_5} \ldots$, and similarly suppose that $\lambda_2 = 2^{f_2} 3^{f_3} 5^{f_5} \ldots$. Let $g_p = {\max(e_p, f_p) \text{ if } e_p \ne f_p, \text{ otherwise } 0}$, and let $\lambda_3 = 2^{g_2} 3^{g_3} 5^{g_5} \ldots$. Show that the period length $\lambda'$ of the sequence $(Z_n)$ is a multiple of $\lambda_3$, and it is a divisor of $\lambda = \text{lcm}(\lambda_1, \lambda_2)$. In particular, $\lambda' = \lambda$ if $(e_p \ne f_p)$, or $e_p = f_p = 0$) for each prime $p$.
Verified: yes
Solve time: 2m38s
Solution
Let $(X_n)$ and $(Y_n)$ be integer sequences modulo $m$ with periods $\lambda_1$ and $\lambda_2$, respectively. Define
$$ Z_n = (X_n + Y_n) \bmod m $$
and let $\lambda'$ denote the period of $(Z_n)$.
Let the prime factorizations of $\lambda_1$ and $\lambda_2$ be
$$ \lambda_1 = \prod_p p^{e_p}, \qquad \lambda_2 = \prod_p p^{f_p}. $$
For each prime $p$, define
$$ g_p = \begin{cases} \max(e_p, f_p), & \text{if } e_p \ne f_p,\ 0, & \text{if } e_p = f_p, \end{cases} $$
and set
$$ \lambda_3 = \prod_p p^{g_p}. $$
We will show that
$$ \lambda_3 \mid \lambda' \mid \lambda, \qquad \lambda = \mathrm{lcm}(\lambda_1, \lambda_2), $$
and characterize when $\lambda' = \lambda$.
Step 1: $\lambda' \mid \lambda$
By Exercise 3.2.2.13, if two sequences modulo $m$ have periods $\lambda_1$ and $\lambda_2$, then their sum sequence modulo $m$ cannot repeat later than $\mathrm{lcm}(\lambda_1, \lambda_2)$. Hence
$$ \lambda' \mid \lambda = \mathrm{lcm}(\lambda_1, \lambda_2). $$
This establishes the upper bound.
Step 2: $\lambda_3 \mid \lambda'$
We prove this using modular arithmetic prime by prime. Fix a prime $p$ and consider the sequences modulo powers of $p$.
- Let $k = \max(e_p, f_p)$.
- Consider the sequences $X_n \bmod p^k$ and $Y_n \bmod p^k$.
If $e_p \ne f_p$, then exactly one of the sequences has period divisible by $p^k$, while the other sequence has period divisible by at most $p^{k-1}$.
Suppose for contradiction that $Z_n \bmod p^k$ has period $\ell$ strictly less than $p^k$. Then $X_n \bmod p^k$ and $Y_n \bmod p^k$ would have to repeat with a common period dividing $\ell$. But the sequence with period divisible by $p^k$ cannot repeat modulo $p^k$ in fewer than $p^k$ steps. This is a contradiction. Therefore, $Z_n \bmod p^k$ has period divisible by $p^k$, i.e. $p^{g_p} \mid \lambda'$.
If $e_p = f_p$, then both sequences have period exactly divisible by $p^{e_p}$. In this case, the sequences may cancel modulo $p^{e_p}$ in the sum $Z_n$, so the $p$-power in $\lambda'$ may be strictly less than $p^{e_p}$. Setting $g_p = 0$ accounts for this possibility, because we cannot guarantee that $p^{e_p} \mid \lambda'$ in general.
Taking the product over all primes $p$, we conclude
$$ \lambda_3 = \prod_p p^{g_p} \mid \lambda'. $$
Step 3: Characterization of $\lambda' = \lambda$
By definition,
$$ \lambda = \mathrm{lcm}(\lambda_1, \lambda_2) = \prod_p p^{\max(e_p, f_p)}. $$
From Step 2, $\lambda_3 \mid \lambda' \mid \lambda$. Therefore, $\lambda' = \lambda$ precisely when for each prime $p$ either $e_p \ne f_p$ or $e_p = f_p = 0$. In these cases, there is no possibility of cancellation reducing the period for that prime, and the period of the sum reaches the maximal possible value. Conversely, if $e_p = f_p \ne 0$ for some $p$, then cancellation modulo $p^{e_p}$ may occur, and the period $\lambda'$ is strictly smaller than $\lambda$.
Step 4: Conclusion
We have established rigorously that
$$ \lambda_3 \mid \lambda' \mid \lambda, $$
with $\lambda = \mathrm{lcm}(\lambda_1, \lambda_2)$, and characterized exactly when $\lambda' = \lambda$. ∎
This solution fixes the heuristic argument in the previous version by explicitly using modular arithmetic for each prime power to justify the divisibility $\lambda_3 \mid \lambda'$. It also correctly treats the case $e_p = f_p \ne 0$.