I am studying Linear Congruential Generators (LCG). In the proof of the main theorem of these generators:
Theorem: The sequence defined by $X_{n+1}=(aX_n+c) \;mod\;m$, has full period $m$, provided that:
$(i)$ $c$ is relatively prime to $m$
$(ii)$ $a\equiv 1 \pmod{p}$ if $p$ is a prime factor of $m$.
$(iii)$ $a\equiv 1 \pmod {4} $, if 4 is a factor of $m$
Thet sequence can be written as
$$
\frac{(a^n-1)(x_0(a-1)+c)}{a-1}\equiv 0\pmod{m}
$$
To reduce that expression to the following:
$$
\frac{(a^n-1)}{a-1}\equiv 0\pmod{m}
$$
The author says that that can be done because due to "the conditions of the theorem (I think $i$ and $ii$), $x_0(a-1)+c$ is relatively prime to $m$.
Why that's true? And why with that can the congruence be simplified?
Best Answer
A $1$-line proof shows $\,b+c\,$ is coprime to $m$ if every prime factor $p$ of $m$ divides $b$ or $c$ but not both. OP is special case: all $\,p\mid b\! =\! x_0(a\!-\!1)\,$ by $\,p\mid a\!-\!1;\,$ no $\,p\mid c\,$ (else $\,p\mid c,m\,$ contra $c,m$ coprime).
Remark $ $ As explained in the linked post. this simple idea (going back to Stieltjes) allows us to generalize Euclid's proof of infinitely many primes to a proof of infinitely many $\rm\color{#c00}{co}primes$ in an arithmetic progression (a much simpler $\rm\color{#c00}{co}prime$ analog of Dirichlet's famous theorem). This very simple result is often overlooked — leading to more complex and less conceptual proofs.