TAOCP 3.2.1.2 Exercise 2

Let $m = 2^e$, where $e \ge 1$.

taocpmathematicsalgorithmsvolume-2medium

Section 3.2.1.2: Choice of Multiplier

Exercise 2. ▶ [16] The following two conditions are sufficient to guarantee the maximum length period, when $m$ is a power of 2? "(i) $c$ is odd; (ii) $a \bmod 4 = 1$."

Verified: yes
Solve time: 1m14s

Solution

Let $m = 2^e$, where $e \ge 1$. The linear congruential sequence is defined by

$X_{n+1} = (aX_n + c) \bmod m.$

According to Theorem A, the sequence has period length $m$ if and only if the following 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$.

Since $m = 2^e$, the only prime dividing $m$ is $p = 2$, and $m$ is divisible by $4$ whenever $e \ge 2$. Condition (i) therefore requires $c$ to be odd. Condition (ii) requires $a - 1$ to be even. Condition (iii) requires $a - 1$ to be divisible by $4$ when $e \ge 2$.

The two given conditions in the exercise are:

  1. $c$ is odd.
  2. $a \bmod 4 = 1$, equivalently $a - 1 \equiv 0 \pmod{4}$.

If $e = 1$, then $m = 2$, condition (iii) is vacuous and condition (ii) reduces to $a - 1 \equiv 0 \pmod{2}$. Condition (ii) is satisfied if $a \bmod 4 = 1$, since $a - 1$ is divisible by $4$ and hence by $2$. Therefore for $e = 1$ the given conditions are sufficient.

If $e \ge 2$, then $m$ is divisible by $4$, and Theorem A requires $a - 1$ to be divisible by $4$ (condition iii). The second condition of the exercise asserts exactly this, $a \bmod 4 = 1$. Condition (i) requires $c$ to be odd, which is the first given condition. Hence both conditions of the exercise together satisfy all necessary requirements of Theorem A for all $e \ge 2$.

Therefore, when $m$ is a power of $2$, the two conditions given in the exercise are sufficient to guarantee that the linear congruential sequence achieves period length $m$.

This completes the proof.

∎