Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
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
up vote 3 down vote accepted

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.

share|cite|improve this answer
That's interesting. I'm curious how the proof of those three lemmas work, but I suppose I shall have to read the paper! Thank you! – Emrakul Apr 17 '13 at 4:20

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.