TAOCP 3.2.1.2 Exercise 3

Let $m = 10^e$ with $e \ge 2$, and let $c$ be odd and not a multiple of 5.

taocpmathematicsalgorithmsvolume-2simple

Section 3.2.1.2: Choice of Multiplier

Exercise 3. [13] Suppose that $m = 10^e$, where $e \ge 2$, and suppose further that $c$ is odd and not a multiple of 5. Show that the linear congruential sequence will have the maximum length period if and only if $a \bmod 20 = 1$.

Verified: yes
Solve time: 1m26s

Solution

Let $m = 10^e$ with $e \ge 2$, and let $c$ be odd and not a multiple of 5. We wish to determine the necessary and sufficient condition on $a$ so that the linear congruential sequence

$X_{n+1} = (a X_n + c) \bmod m$

has period length $m$.

By Theorem A, the linear congruential sequence $(X_0, a, c, m)$ has period length $m$ if and only if the following three conditions hold:

i) $c$ is relatively prime to $m$;

ii) $b = a - 1$ is a multiple of $p$ for every prime $p$ dividing $m$;

iii) $b$ is a multiple of $4$ if $m$ is a multiple of $4$.

First, $m = 10^e = 2^e 5^e$. The prime divisors of $m$ are $2$ and $5$, and $m$ is divisible by $4$ whenever $e \ge 2$.

Condition (i) requires $\gcd(c, m) = 1$. Since $c$ is odd, it is not divisible by $2$, and since $c$ is not a multiple of $5$, it is not divisible by $5$. Therefore $c$ is relatively prime to $10^e$, and condition (i) is satisfied.

Condition (ii) requires $b = a - 1$ to be divisible by each prime factor of $m$. That is, we must have

$a - 1 \equiv 0 \pmod{2} \quad \text{and} \quad a - 1 \equiv 0 \pmod{5}.$

Equivalently,

$a \equiv 1 \pmod{2} \quad \text{and} \quad a \equiv 1 \pmod{5}.$

Condition (iii) requires $b = a - 1$ to be divisible by 4 because $m$ is divisible by 4. Therefore

$a - 1 \equiv 0 \pmod{4} \quad \Longleftrightarrow \quad a \equiv 1 \pmod{4}.$

Combining conditions (ii) and (iii), we have

$a \equiv 1 \pmod{4} \quad \text{and} \quad a \equiv 1 \pmod{5}.$

By the Chinese Remainder Theorem, there is a unique solution modulo $\operatorname{lcm}(4,5) = 20$. Therefore, the necessary and sufficient condition on $a$ is

$a \equiv 1 \pmod{20}.$

Thus, the linear congruential sequence has period length $m = 10^e$ if and only if $a \bmod 20 = 1$.

This completes the proof. ∎