= Full-period criterion for a mixed congruential generator
{title2=$\operatorname{period}=M$}
= Hull–Dobell theorem
{c}
{synonym}
A <linear congruential generator> has period $M$ for every seed if and only if $\gcd(c,M)=1$, every prime dividing $M$ divides $a-1$, and $4\mid M$ implies $4\mid a-1$. The coprimality of $c$ prevents the orbit from being trapped in a residue class; the multiplier conditions permit full-period lifting through each prime power. Combining the prime-power periods by the <Chinese remainder theorem> gives period $M$. For $M=12^k=2^{2k}3^k$, the multiplier criterion reduces to $a\equiv1\pmod{12}$, together with $\gcd(c,6)=1$. A positive increment alone is insufficient.
Back to article page
