# Why do prime numbers in modulo result in more uniform distributions?

Let us assume a sequence as follows:

$S_{n} = (S_{n-1} * c_{1} + c_{2})\text{ mod } m$

This is the pseudorandom generator found in most programming languages' random function.

It is known that a prime $m$ results in a more uniform distribution of random numbers, as a result of a larger period for $S_{n}$. As a result, $m$ is typically a prime number.

Why do prime numbers typically result in larger periods than factorable numbers for modulo arithmetic?

-
Have you seen the closed form formula for $S_n$? – Gerry Myerson Apr 16 '13 at 6:03
@GerryMyerson I haven't; I'll look that up. – Emrakul Apr 16 '13 at 6:04

According to Wikipedia, the period is at most $m$, and is equal to $m$ only if
1. $\gcd(c_2,m)=1$,
2. $p\mid m$ implies $p\mid c_1-1$ for all prime $p$, and
3. $4\mid m$ implies $4\mid c_1-1$.
So $m$ needn't be prime, but it's easiest to meet and to check these conditions if it is.