TAOCP 3.2.1.3 Exercise 5
Let $m = p_1^{e_1} \cdots p_r^{e_r}$ and $a = 1 + k p_1^{f_1} \cdots p_r^{f_r}$, where $k$ is relatively prime to $m$, and $a$ satisfies the conditions of Theorem 3.
Exercise 5. [M20] Given that $m = p_1^{e_1} \cdots p_r^{e_r}$ and $a = 1 + kp_1^{f_1} \cdots p_r^{f_r}$, where $a$ satisfies the conditions of Theorem 3.2.1.2A and $k$ is relatively prime to $m$, show that the potency is $\max(\lceil e_i/f_i \rceil) = \lceil e_1/f_1 \rceil)$.
Verified: yes
Solve time: 1m23s
Solution
Let $m = p_1^{e_1} \cdots p_r^{e_r}$ and $a = 1 + k p_1^{f_1} \cdots p_r^{f_r}$, where $k$ is relatively prime to $m$, and $a$ satisfies the conditions of Theorem 3.2.1.2A. We are asked to determine the potency of the linear congruential generator with modulus $m$ and multiplier $a$.
By definition (Section 3.2.1.3), the potency $s$ is the least positive integer such that
$$ b^s \equiv 0 \pmod{m}, $$
where $b = a - 1 = k p_1^{f_1} \cdots p_r^{f_r}$. Since $k$ is relatively prime to $m$, the prime-power factors of $b$ are precisely $p_1^{f_1}, \dots, p_r^{f_r}$.
We examine the divisibility of $b^s$ by each prime power $p_i^{e_i}$ separately. Consider an arbitrary $i$ with $1 \le i \le r$. We have
$$ b^s = \bigl(k \cdot p_1^{f_1} \cdots p_r^{f_r}\bigr)^s = k^s \cdot p_1^{s f_1} \cdots p_r^{s f_r}. $$
Since $k$ is relatively prime to $p_i$, $k^s$ contributes no additional factor of $p_i$. Therefore, the exponent of $p_i$ in $b^s$ is $s f_i$. To ensure that $b^s$ is divisible by $p_i^{e_i}$, we must have
$$ s f_i \ge e_i \implies s \ge \frac{e_i}{f_i}. $$
Because $s$ must be an integer, the minimal $s$ satisfying this inequality for all $i$ is
$$ s = \max_{1 \le i \le r} \left\lceil \frac{e_i}{f_i} \right\rceil. $$
This establishes that the potency is
$$ \boxed{s = \max(\lceil e_1/f_1 \rceil, \dots, \lceil e_r/f_r \rceil)}. $$
If we assume the indices are ordered so that $\lceil e_1/f_1 \rceil \ge \lceil e_i/f_i \rceil$ for all $i$, then the potency simplifies to
$$ s = \lceil e_1 / f_1 \rceil. $$
This completes the proof. ∎