# Thread: Period of modulo sequence? (linear congruential random generator)

1. ## Period of modulo sequence? (linear congruential random generator)

Consider the following sequence of natural numbers:

$x_{i+1} = (a \cdot x_i + c) \mod m$

With certain constants a, c and m. Also known as the Linear Congruential (Random) Generator because it's used to generate pseudo-random numbers. For sake of simplicity assume $x_0$=0.

Example with a=2, c=1, m=5: $x_i$ = 0,1,3,2,0,1,3,2,...etc

In this case the sequence has a period of 4. Obviously in any case the period is at most m.

I'm wondering for which numbers of m, there exist a>1 and c so that the maximum period m is actually obtained (with a=1 this is always possible for any m, the sequence then simply becomes 0,c,2c,3c,etc..).

The first possibility seems to be m=8, for example with a=5 and b=3: $x_i$ = 0,3,2,5,4,7,6,1,(0,3,etc)

The wiki link above suggests this ought to be possible for any m, as long as the following criteria are met:
• c and m are coprime
• a-1 is divisible by all prime factors of m
• a-1 is a multiple of 4 $\Leftrightarrow$ m is a multiple of 4

But in practice I found otherwise (for starters, there are no values a,c at all for m<8).

Does anyone know more about this? I do have some vague idea as to what criterium m should meet in order to have this "full modulo period" property. But I'm not sure yet and certainly unable to prove anything.

2. A starting point could be to first solve the recurrence relation:

[LaTeX ERROR: Convert failed]

So [LaTeX ERROR: Convert failed]
Then [LaTeX ERROR: Convert failed]

In general [LaTeX ERROR: Convert failed] where we've used the formula for the geometric sum. Now after modding out m, we need to be left with m distinct numbers

To show that they are all different, I think you need to use something of the sort: [LaTeX ERROR: Convert failed]

3. Thanks, nice start. I'm not that good with modulo calculations.

Originally I mentioned we could assume $x_0$=0, but this isn't necessary: if some combination of a, c and m results in a full period, it does so for any $x_0$.

And since $x_t=a^tx_0+c\frac{a^t-1}{a-1}$ perhaps we can pick $x_0$ so that $x_t$ becomes easier to resolve (mod m)...?