TAOCP 3.2.1 Exercise 2

Section 3.2.1: The Linear Congruential Method

Exercise 2. ▶ [M20] Show that if $a$ and $m$ are relatively prime, the number $X_0$ will always appear in the period.

Verified: yes
Solve time: 4m21s

---

Solution

Let

$$ X_{n+1}\equiv aX_n+c \pmod m, $$

and assume that

$$ (a,m)=1. $$

We must show that $X_0$ belongs to the periodic part of the sequence, that is, there exists $k>0$ such that

$$ X_k\equiv X_0 \pmod m. $$

Consider the mapping

$$ f(x)\equiv ax+c \pmod m $$

on the set of residue classes modulo $m$.

Since $(a,m)=1$, multiplication by $a$ is invertible modulo $m$. Hence, if

$$ f(x_1)\equiv f(x_2)\pmod m, $$

then

$$ ax_1+c\equiv ax_2+c\pmod m, $$

so

$$ a(x_1-x_2)\equiv 0\pmod m. $$

Because $a$ has a multiplicative inverse modulo $m$, it follows that

$$ x_1\equiv x_2\pmod m. $$

Thus $f$ is injective. Since the set of residue classes modulo $m$ is finite, $f$ is therefore bijective. In other words, $f$ is a permutation of the $m$ residue classes.

Now consider the orbit of $X_0$:

$$ X_0,\ X_1=f(X_0),\ X_2=f(X_1),\ldots . $$

Because there are only $m$ residue classes, some value must repeat. Let $r>s\ge0$ be such that

$$ X_r=X_s. $$

Applying the inverse permutation $f^{-1}$ repeatedly, $s$ times, gives

$$ X_{r-s}=X_0. $$

Indeed,

$$ X_r=f^{,r-s}(X_s), $$

and since $X_r=X_s$,

$$ f^{,r-s}(X_s)=X_s. $$

Applying $f^{-s}$ to both sides yields

$$ f^{,r-s}(X_0)=X_0, $$

that is,

$$ X_{r-s}=X_0. $$

Since $r-s>0$, we have found a positive integer $k=r-s$ such that

$$ X_k\equiv X_0 \pmod m. $$

Therefore $X_0$ lies on a cycle of the permutation $f$, and hence $X_0$ always appears in the period.

$$ \boxed{\text{If }(a,m)=1,\text{ then }X_0\text{ always appears in the period.}} $$

∎