Period of linear congruential generator How can you calculate the probability distribution of the period length of a linear congruential generator? That is $X_{n+1} = (aX_n + c) \bmod m$ where $a$ is chosen uniformly at random from $\{1,\dots, m-1\}$ and $c$ is chosen uniformly at random from  $\{0,\dots, m-1\}$ and $m$ is a fixed prime.   Take $X_0$ to be some arbitrary value from $\{0,\dots, m-1\}$.
If it is hard to do exactly, is it possible to give good bounds for the cdf?
 A: This may not address the question exactly, but the results derived indicate that the final answer may depend on the factors common to $a-1$ and $m$.

A preliminary lemma and theorem

Lemma: Suppose $p$ is prime and $j\ge2$. Then, unless $p=j=2$,
  $$
p^k\,|\,n\implies\left.p^{k-j+2}\,\middle|\,\binom{n}{j}\right.\tag{1}
$$
  Furthermore,
  $$
2^k\,|\,n\implies\left.2^{k-1}\,\middle|\,\binom{n}{2}\right.\tag{2}
$$

Proof: Unless $p=j=2$, $j\lt p^{j-1}$.  Thus, $j$ has at
most $j-2$ factors of $p$. Then $(1)$ follows from the binomial identity
$$
\binom{n}{j} = \frac nj\binom{n-1}{j-1}
$$
$(2)$ follows from
$$
\binom{n}{2}=\frac n2(n-1)
$$
$\square$


Theorem: Suppose that
  $$
\begin{align}
&\text{(a) for all primes $p$, }p\mid m\implies p\mid a-1\\
&\text{(b) }4\mid m\implies4\mid a-1
\end{align}
$$
  Then,
  $$
\left.m\,\middle|\,\frac{a^n-1}{a-1}\right.\implies m\,|\,n
$$

Proof: Assume $\left.m\,\middle|\,\dfrac{a^n-1}{a-1}\right.$. For simplicity of notation, let $r=a-1$. Then
$$
\frac{a^n-1}{a-1}=\sum_{j=1}^n\binom{n}{j}r^{j-1}\tag{3}
$$
For any odd $p\,|\,m$, assume that $p^k\,|\,n$ and $\left.p^{k+1}\,\middle|\,\dfrac{a^n-1}{a-1}\right.$. Using $(3)$, we get
$$
n\equiv-\sum_{j=2}^n\binom{n}{j}r^{j-1}\pmod{p^{k+1}}\tag{4}
$$
The Lemma and the assumption that $p\,|\,m\implies p\,|\,r$ says that $p^{k-j+2}p^{j-1}=p^{k+1}$ divides each term in $(4)$. Thus, $p^{k+1}\,|\,n$. Bootstrapping, we get that for any odd $p\,|\,m$,
$$
\left.p^k\,\middle|\,\frac{a^n-1}{a-1}\right.\implies p^k\,|\,n\tag{5}
$$
If $2\,|\,m$, then $\left.2\,\middle|\,\dfrac{a^n-1}{a-1}\right.$. Using $(3)$, we get
$$
n\equiv-\sum_{j=2}^n\binom{n}{j}r^{j-1}\pmod{2}\tag{6}
$$
The assumption that $p\,|\,m\implies p\,|\,r$ says that $2$ divides each term in $(6)$. Thus, $2\,|\,n$; that is,
$$
\left.2\,\middle|\,\frac{a^n-1}{a-1}\right.\implies2\,|\,n\tag{7}
$$
If $4\,|\,m$, then assume that $2^k\,|\,n$ and that $\left.2^{k+1}\,\middle|\,\dfrac{a^n-1}{a-1}\right.$. Using $(3)$, we get
$$
n\equiv-\sum_{j=2}^n\binom{n}{j}r^{j-1}\pmod{2^{k+1}}\tag{8}
$$
The Lemma and the assumption that $4\,|\,m\implies4\,|\,r$ says that $2^{k-j+1}4^{j-1}=2^{k+j-1}$ divides each term in $(8)$. Since $j\ge2$, we have $2^{k+1}\,|\,n$. Bootstrapping, we get that
$$
\left.2^k\,\middle|\,\frac{a^n-1}{a-1}\right.\implies 2^k\,|\,n\tag{9}
$$
$(5)$ and either $(7)$ or $(9)$ show that
$$
\left.m\,\middle|\,\frac{a^n-1}{a-1}\right.\implies m\,|\,n\tag{10}
$$
$\square$

Suppose the sequence $x_k$ is defined by the recurrence
$$
x_{k+1}=ax_k+b\tag{11}
$$
then, inductively, we have
$$
x_k=a^kx_0+\frac{a^k-1}{a-1}b\tag{12}
$$
Multiplying by $a-1$ and adding $1$ yields
$$
\frac{a^{k_1}-1}{a-1}\equiv\frac{a^{k_2}-1}{a-1}\pmod{m}\implies a^{k_1}\equiv a^{k_2}\pmod{m}\tag{13}
$$
Therefore, to investigate the periodicity of $x_k$, we look at the periodicity of $\dfrac{a^k-1}{a-1}\bmod{m}$.

To maximize the range of $x_k$ ,we will assume that $(a,m)=(b,m)=1$. This implies
$$
\begin{align}
\frac{a^{k_1}-1}{a-1}\equiv\dfrac{a^{k_2}-1}{a-1}\pmod{m}
&\implies\frac{a^{k_1-k_2}-1}{a-1}a^{k_2}\equiv0\pmod{m}\\[6pt]
&\implies\frac{a^{k_1-k_2}-1}{a-1}\equiv0\pmod{m}\tag{14}
\end{align}
$$
That is, the period of $x_k$ is the smallest positive $n$ for which
$$
\frac{a^n-1}{a-1}\equiv0\pmod{m}\tag{15}
$$
By the theorem above, $m\,|\,n$ and since there are only $m$ residue classes $\bmod{\,m}$, we must have $n=m$. Thus,

Theorem: Suppose
  $$
\begin{align}
&\text{(a) for all primes $p$, }p\mid m\implies p\mid a-1\\
&\text{(b) }4\mid m\implies4\mid a-1\\
&\text{(c) }\gcd(b,m)=1
\end{align}
$$
  Then the modular sequence defined by
  $$
x_{n+1}\equiv ax_n+b\pmod{m}
$$
  has period $m$.

A: There's not much of a distribution there. The period is $1$ if $a=1$ and $c=0$ or if $a\ne1$ and $X_0=c/(1-a)$; otherwise it's $m-1$.
