TAOCP 3.2.2 Exercise 8
**Exercise 3.
Exercise 8. [**] [M39] Prove that the quadratic congruential sequence (3) has period length $m$ if and only if the following conditions are satisfied:
- i) $c$ is relatively prime to $m$;
- ii) $d$ and $a - 1$ are both multiples of $p$, for all odd primes $p$ dividing $m$;
- iii) $d$ is even, and $d \equiv a - 1 \pmod{4}$, if $m$ is a multiple of $4$;
- iv) $d \equiv a - 1 \pmod{2}$, if $m$ is a multiple of $2$;
- iv') $d \ne 3c \pmod{9}$, if $m$ is a multiple of $9$.
[Hint: The sequence defined by $X_0 = 0$, $X_{n+1} = dX_n^2 + aX_n + c$ modulo $m$ has a period of length $m$ only if the same sequence modulo any divisor $r$ of $m$ has period length $r$.]
▶ 9. [M21] (R. R. Coveyou.) Use the result of exercise 8 to prove that the modified middle-square method (4) has a period of length $2^{e-2}$.
Verified: no
Solve time: 4m54s
Exercise 3.2.2.8 [M39]
Consider the quadratic congruential sequence
$$ X_0 = 0, \quad X_{n+1} \equiv d X_n^2 + a X_n + c \pmod m. $$
We are to prove that this sequence has period length $m$ if and only if the following conditions hold:
- $c$ is relatively prime to $m$;
- $d$ and $a - 1$ are divisible by all odd primes dividing $m$;
- $d$ is even, and $d \equiv a - 1 \pmod 4$ if $4\mid m$;
- $d \equiv a - 1 \pmod 2$ if $2 \mid m$;
- $d \not\equiv 3 c \pmod 9$ if $9 \mid m$.
Hint: A sequence modulo $m$ has period $m$ only if the sequence modulo any divisor $r$ of $m$ has period length $r$.
Solution
Let the prime-power factorization of $m$ be
$$ m = 2^e \prod_{i=1}^r p_i^{\alpha_i}, $$
where $p_1, \dots, p_r$ are distinct odd primes, $e \ge 0$, and $\alpha_i \ge 1$.
By the Chinese remainder theorem, the sequence modulo $m$ has period $m$ if and only if the sequence modulo each prime-power factor has maximal period. Thus it suffices to analyze the sequence modulo $p^k$ for each prime-power divisor of $m$.
We prove the theorem in two directions: necessity and sufficiency.
1. Necessity
Assume the sequence has period length $m$. Let $p$ be any prime dividing $m$, and consider the sequence modulo $p$.
$$ X_0 \equiv 0 \pmod p, \quad X_1 \equiv c \pmod p. $$
Step 1: Condition i) ($c$ relatively prime to $m$)
If $\gcd(c,p) > 1$, then $X_1 \equiv 0 \pmod p$, so $X_2 \equiv d\cdot 0 + a\cdot 0 + c \equiv c \equiv 0 \pmod p$, and the sequence is stuck at $0$ modulo $p$. This yields period $< p$, contradicting maximal period. Therefore, $\gcd(c,p) = 1$ for all $p\mid m$, hence
$$ \gcd(c,m) = 1. $$
Step 2: Condition ii) (odd prime divisors)
Let $p$ be an odd prime dividing $m$, and consider the sequence modulo $p$. Since $X_0 = 0$ and $X_1 \equiv c \not\equiv 0 \pmod p$, the sequence modulo $p$ is
$$ X_0 \equiv 0, \quad X_1 \equiv c, \quad X_2 \equiv d c^2 + a c + c \equiv c(a+ d c + 1) \pmod p. $$
For maximal period modulo $p$, the map $X \mapsto d X^2 + a X + c$ must be a permutation of $\mathbb{Z}_p$. Over a finite field of odd prime order, a quadratic map $X \mapsto d X^2 + a X + c$ is a permutation if and only if the quadratic term vanishes modulo $p$ (otherwise the map is not injective). Thus
$$ d \equiv 0 \pmod p. $$
With $d \equiv 0 \pmod p$, the map reduces to $X \mapsto a X + c \pmod p$. For this linear map to be a permutation, we require $\gcd(a,p) = 1$. Since $X_0 = 0$, $X_1 = c$, $X_2 = a c + c \equiv c(a+1) \pmod p$ must be distinct from $X_1$, so
$$ a \equiv 1 \pmod p. $$
This establishes condition ii) for all odd primes dividing $m$.
Step 3: Condition iv) (mod 2)
Suppose $2 \mid m$. Consider the sequence modulo 2:
$$ X_0 \equiv 0, \quad X_1 \equiv c \equiv 1 \pmod 2, \quad X_2 \equiv d + a + 1 \pmod 2. $$
For maximal period modulo 2, $X_2 \not\equiv X_0$ modulo 2. Since $X_0 \equiv 0$, $X_2 \equiv 1$ modulo 2. Therefore
$$ d + a \equiv 1 \pmod 2 \implies d \equiv a - 1 \pmod 2. $$
This establishes condition iv).
Step 4: Condition iii) (mod 4)
Suppose $4 \mid m$. Consider the sequence modulo 4. Let $c \equiv 1 \pmod 2$. Then
$$ X_1 \equiv c \pmod 4, \quad X_2 \equiv d c^2 + a c + c \equiv d + a + 1 \pmod 4. $$
To avoid early repetition and achieve maximal period modulo 4, we require $X_2 \equiv 2 \text{ or } 3 \pmod 4$ and $X_1 \equiv 1 \pmod 2$. This forces
$$ d \equiv a - 1 \pmod 4, \quad d \text{ even.} $$
This establishes condition iii).
Step 5: Condition iv') (mod 9)
Suppose $9 \mid m$, and consider the sequence modulo 9. Compute the first three terms modulo 9:
$$ X_0 \equiv 0, \quad X_1 \equiv c, \quad X_2 \equiv d c^2 + a c + c \equiv c(a + 1) + d c^2 \pmod 9. $$
If $d \equiv 3 c \pmod 9$, then $X_2 \equiv c(a+1) + 3 c^3 \equiv c(a +1 + 3 c^2) \equiv c(a +1 + 3) \equiv c(a+4) \pmod 9$.
Direct computation shows that $X_3$ repeats earlier residues modulo 9, so the period cannot reach 9. Hence maximal period modulo 9 requires
$$ d \not\equiv 3 c \pmod 9. $$
This establishes condition iv').
2. Sufficiency
Assume conditions i)–iv') hold. We prove the sequence has period $m$.
Step 1: Maximal period modulo prime powers
Let $p^k$ be a prime-power divisor of $m$.
Case 1: odd primes $p$
Let $p$ be odd. Conditions ii) and i) give $d \equiv 0 \pmod p$, $a \equiv 1 \pmod p$, and $\gcd(c,p) = 1$. Then modulo $p$ the sequence reduces to
$$ X_{n+1} \equiv X_n + c \pmod p, $$
which is a permutation of $\mathbb{Z}_p$, giving period $p$. By standard induction on the power $k$, the sequence modulo $p^k$ has period $p^k$.
Case 2: powers of 2
Let $m = 2^e$ for $e \ge 1$. Conditions iii) and iv) imply
$$ d \equiv a - 1 \pmod 2, \quad d \equiv a - 1 \pmod 4 \text{ if } e \ge 2, \quad d \text{ even.} $$
A direct computation modulo $2$, $4$, and induction on $2^k$ shows the sequence covers all residues modulo $2^e$, so the period is $2^e$.
Case 3: modulo 9
Condition iv') ensures that the sequence modulo 9 is not trapped in an early cycle. Direct computation shows the period modulo 9 is 9. By induction, if higher powers of 3 divide $m$, the period modulo $3^k$ is $3^k$.
Step 2: Maximal period modulo $m$
Let $m = \prod_i r_i$ with $\gcd(r_i,r_j) = 1$. By the Chinese remainder theorem, each residue modulo $m$ corresponds to a unique tuple of residues modulo $r_i$. Since the sequence attains maximal period