Linear congruential generator

Remarks

Example: $m = 8$, $a = 5$, $c = 1$, $X_0 = 0$. The states are $0, 1, 6, 7, 4, 5, 2, 3, 0, \ldots$, for instance $5 \cdot 7 + 1 = 36 \equiv 4 \pmod 8$; all $8$ residues appear, so the period is $m$. Non-example: $X_{n+1} = X_n^2 \bmod m$ is not a linear congruential generator, because the map $x \mapsto x^2$ is not of the form $x \mapsto ax + c$. The map $x \mapsto ax + c$ is an affine map of the ring of integers modulo $m$, so the period is at most $m$. The Hull–Dobell theorem treats $c \ne 0$. The period equals $m$ for every seed if and only if three conditions hold. They are: $c$ and $m$ are coprime, every prime factor of $m$ divides $a - 1$, and $4$ divides $a - 1$ if $4$ divides $m$. In the example, $\gcd(1, 8) = 1$ and $a - 1 = 4$, so the conditions hold.