TAOCP 3.2.1.3 Exercise 3
The potency is the least integer $s$ such that b^s \equiv 0 \pmod{m}, where $b=a-1$; equivalently, $m\mid b^s$.
Exercise 3. [11] When $m = 2^{35}$, what is the potency of the linear congruential sequence with $a = 3141592621$? What is the potency if the multiplier is $a = 2^{23} + 2^{13} + 2^7 + 1$?
Verified: yes
Solve time: 1m28s
Solution
The potency is the least integer $s$ such that
$$ b^s \equiv 0 \pmod{m}, $$
where $b=a-1$; equivalently, $m\mid b^s$.
Here $m=2^{35}$.
For the multiplier $a=3141592621$,
$$ b=a-1=3141592620. $$
Since
$$ 3141592620=4\cdot 785398155, $$
and $785398155$ is odd, we have
$$ v_2(b)=2. $$
Therefore
$$ v_2(b^s)=2s. $$
The condition $2^{35}\mid b^s$ is equivalent to
$$ 2s\ge 35. $$
The least such $s$ is
$$ s=\left\lceil \frac{35}{2}\right\rceil=18. $$
Hence the potency is $18$.
For the multiplier
$$ a=2^{23}+2^{13}+2^7+1, $$
we have
$$ b=a-1=2^{23}+2^{13}+2^7 =2^7(2^{16}+2^6+1). $$
Since
$$ 2^{16}+2^6+1=65536+64+1=65601 $$
is odd,
$$ v_2(b)=7. $$
Therefore
$$ v_2(b^s)=7s. $$
The condition $2^{35}\mid b^s$ is equivalent to
$$ 7s\ge 35. $$
The least such $s$ is
$$ s=5. $$
Hence the potency is $5$.
Thus the answers are
$$ \boxed{\text{potency}=18 \text{ for } a=3141592621,} $$
and
$$ \boxed{\text{potency}=5 \text{ for } a=2^{23}+2^{13}+2^7+1.} $$