TAOCP 3.2.1.2 Exercise 7

Section 3.2.1.2: Choice of Multiplier

Exercise 7. ▶ [**] [M23] The period of a congruential sequence need not start with $X_0$, but we can always find indices $\mu \ge 0$ and $\lambda > 0$ such that $X_{n+\lambda} = X_n$ whenever $n \ge \mu$, and for which $\mu$ and $\lambda$ are the smallest possible values with this property. (See exercises 3.1-6 and 3.2.1-1.) If $\mu_j$ and $\lambda_j$ are the indices corresponding to the sequences

$$\left(X_0 \bmod p_j^{e_j},\ a \bmod p_j^{e_j},\ c \bmod p_j^{e_j}\right),$$

and if $\mu$ and $\lambda$ correspond to the composite sequence $(X_0, a, c, p_1^{e_1} \ldots p_t^{e_t})$. Lemma Q states that $\lambda$ is the least common multiple of $\lambda_1, \ldots, \lambda_t$. What is the value of $\mu$ in terms of the values of $\mu_1, \ldots, \mu_t$? What is the maximum possible value of $\mu$ obtainable by varying $X_0$, $a$, and $c$, when $m = p_1^{e_1} \cdots p_t^{e_t}$ is fixed?

Verified: yes
Solve time: 3m12s

---

Let

$$ X_{n+1}\equiv aX_n+c \pmod m,\qquad m=\prod_{j=1}^t p_j^{e_j}, $$

and let $X_n^{(j)}$ denote the corresponding sequence modulo $p_j^{e_j}$. For each $j$, let $\mu_j,\lambda_j$ be the minimal indices such that

$$ X_{n+\lambda_j}^{(j)}=X_n^{(j)} \qquad (n\ge \mu_j). $$

Let $\mu,\lambda$ be the corresponding indices for the sequence modulo $m$.

Determination of $\mu$

By the Chinese Remainder Theorem,

$$ X_n=X_r \pmod m $$

if and only if

$$ X_n^{(j)}=X_r^{(j)} \pmod{p_j^{e_j}} \qquad (1\le j\le t). $$

Lemma Q gives

$$ \lambda=\operatorname{lcm}(\lambda_1,\ldots,\lambda_t). $$

Set

$$ M=\max(\mu_1,\ldots,\mu_t). $$

If $n\ge M$, then $n\ge\mu_j$ for every $j$, hence

$$ X_{n+\lambda}^{(j)} = X_n^{(j)}, $$

because $\lambda$ is a multiple of $\lambda_j$. Therefore

$$ X_{n+\lambda}=X_n \qquad (n\ge M), $$

so $\mu\le M$.

To prove minimality, suppose that $\mu'<M$. Choose an index $k$ with

$\mu_k=M$. Since $\mu_k$ is minimal, the sequence modulo $p_k^{e_k}$

cannot satisfy

$$ X_{n+\Lambda}^{(k)}=X_n^{(k)} \qquad (n\ge \mu') $$

for any period $\Lambda>0$. Hence the composite sequence modulo $m$ cannot satisfy

$$ X_{n+\Lambda}=X_n \qquad (n\ge \mu'). $$

Thus no smaller value than $M$ is admissible, and

$$ \boxed{\mu=\max(\mu_1,\ldots,\mu_t)}. $$

Maximum possible value of $\mu$ for a prime-power modulus

It remains to determine the largest possible $\mu_j$ for modulus $p^e$.

Write

$$ T(x)=ax+c \pmod{p^e}. $$

The sequence is the orbit

$$ X_n=T^n(X_0). $$

Since $T$ is affine, its functional graph is highly restricted.

Case 1: $p\nmid a$

Then $T$ is a permutation of the $p^e$ residue classes. Every orbit is a cycle, so there is no transient part:

$$ \mu=0. $$

Hence large values of $\mu$ can occur only when $p\mid a$.

Case 2: $p\mid a$

Let

$$ v=v_p(a)\ge1. $$

Then

$$ X_{n+1}-X_n^* \equiv a(X_n-X_n^*) \pmod{p^e}, $$

where $X_n^*$ is any fixed point. Iterating gives

$$ X_n-X^* \equiv a^n(X_0-X^*) \pmod{p^e}. $$

Since $v_p(a)=v$,

$$ v_p(a^n)=nv. $$

Therefore $a^n\equiv0\pmod{p^e}$ as soon as

$$ nv\ge e. $$

Hence every orbit reaches a fixed point after at most

$$ \left\lceil \frac{e}{v}\right\rceil $$

steps. Since $v\ge1$,

$$ \mu\le e. $$

The largest value is obtained when $v=1$, that is, when $a$ is divisible by $p$ but not by $p^2$. Then

$$ \mu\le e. $$

This bound is attained. Take

$$ a=p,\qquad c=0,\qquad X_0=1. $$

Then

$$ X_n=p^n \pmod{p^e}. $$

The values

$$ 1,p,p^2,\ldots,p^{e-1},0 $$

are all distinct, and $0$ is a fixed point. Thus the transient part has length exactly $e$:

$$ \mu=e. $$

Consequently, for modulus $p^e$,

$$ \boxed{\max \mu=e}. $$

Maximum possible value for general $m$

For each prime-power factor $p_j^{e_j}$,

$$ \max \mu_j=e_j. $$

Since

$$ \mu=\max(\mu_1,\ldots,\mu_t), $$

the largest possible value of $\mu$ is obtained by maximizing one component and taking the others arbitrary. Therefore

$$ \boxed{\mu_{\max} = \max_{1\le j\le t} e_j}. $$

Thus

$$ \boxed{\mu=\max(\mu_1,\ldots,\mu_t)}, \qquad \boxed{\max \mu=\max_{1\le j\le t} e_j}. $$

These are the required answers.