# Linear Congruential Generator of length 5

For educational purpose, I need a very short random number generator. Then I tried to use a linear consequential generator with modulo equal to 5, expecting a length (period) equal to 5.

Following the rules described in https://en.wikipedia.org/wiki/Linear_congruential_generator#c%E2%89%A00 , I choose :

$a=4$, $c=1$, $m=5$ and $X_0=0$.

These values generate the sequence 1 0 1 0 1...

$X_0=2$ generates 4 2 4 2... and $X_0$=3 generates 3 3 3...

I do not understand which rule I infringe as :

• 1st rule : $m$ being a prime number, any $c$ would be prime with it ;

• 2nd rule : $m$ being a prime number, it has no prime factors, then any $a$ would be right

• 3nd rule does not apply as $m$ is not a multiple of 4

Obviously, I am wrong.

I would appreciate any comment.

The period is a factor of $$\phi(m)$$. To get the maximum period, $$\phi(m)$$, $$a$$ must be a primitive root modulo $$m$$. If $$m$$ is prime, $$\phi(m)=m-1$$.
Modulo 5, $$4=-1$$ is not a primitive root, but has order 2. Hence your observation that the sequence of numbers coming from your generator has period 2.
Picking $$a$$ from a particular residue class mod 4 is no guarantee of success (nor of failure). Perhaps OP was thinking of the advice for picking parameters for a LCG when $$m$$ is a power of 2? Then indeed, $$a=1\mod 4$$ is best, and will give a period of $$\phi(m)=m/2$$.